O(1) Space O(n) Time in C#. 2 Passes


  • 0
    S
    public int LongestValidParentheses3(string srcStr)
    {
        int longest = 0;
        int extra = 0;
        int length = 0;
    
        for (int index = 0; index < srcStr.Length; index++)
        {
            GetLongestStr(srcStr, index, '(', ref extra, ref length, ref longest);
        }
    
        length = 0;
        extra = 0;
    
        for (int index = srcStr.Length - 1; index >= 0; index--)
        {
            GetLongestStr(srcStr, index, ')', ref extra, ref length, ref longest);
        }
    
        return longest;
    }
    
    private void GetLongestStr(string srcStr, int index, char ch, ref int extra, ref int length, ref int longest)
    {
        if (srcStr[index] == ch)
        {
            extra++;
            length++;
        }
        else
        {
            if (extra > 0)
            {
                extra--;
                length++;
                if (extra == 0)
                {
                    longest = Math.Max(longest, length);
                }
            }
            else
            {
                extra = 0;
                length = 0;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.