32. Longest Valid Parentheses

Time: O(n)

Space: O(1)

Problem Overview

A run of parentheses is balanced exactly when it has as many openers as closers and no prefix ever has more closers than openers.

Intuition

A run of parentheses is balanced exactly when it has as many openers as closers and no prefix ever has more closers than openers. Scanning left to right with two counters checks both rules: equal counts mark a balanced run, and extra closers break the run so both counters restart. That pass never sees a run that still has extra openers at the end, such as the one inside "(()". Scanning again from the right with the roles swapped catches those runs, and no stack or array is needed.

Algorithm

1Scan left to right, counting opening and closing parentheses.
2When the counts are equal, record twice the count as a candidate length.
3When closers exceed openers, reset both counters to 0.
4Scan right to left the same way, but reset when openers exceed closers.
5Return the largest length recorded in either pass.

Example Walkthrough

Input: s = ")()())"

1.The first closer has no opener, so the counters reset.
2.The next four characters keep the counts equal at 1 and then 2, so the length reaches 4.
3.The last closer breaks the run and the counters reset again.
4.The right to left pass finds nothing longer.

Output: 4

Common Pitfalls

•One pass is not enough. In "(()" the left pass never sees equal counts, while the right pass finds length 2.
•Reset only when the run becomes impossible to fix, which is extra closers going left to right and extra openers going right to left.
•Record the length when the counts are equal, not when they reset.
•The stack and DP methods also run in linear time but need linear memory. Two counters need constant memory.

32.cs

// Approach: Two counter scans. Left to right, count opens and closes. When
// they are equal the current run is balanced, and when closes exceed opens
// the run is broken, so both counters reset. That pass misses runs that
// still have extra opens at the end, such as "(()", so a right to left pass
// with the roles swapped catches them.
// Time: O(n) Space: O(1)

public class Solution
{
    public int LongestValidParentheses(string s)
    {
        int best = 0;
        int open = 0;
        int close = 0;

        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == '(')
                open++;
            else
                close++;

            if (open == close)
                best = Math.Max(best, 2 * close);
            else if (close > open)
                open = close = 0;
        }

        open = close = 0;
        for (int i = s.Length - 1; i >= 0; i--)
        {
            if (s[i] == '(')
                open++;
            else
                close++;

            if (open == close)
                best = Math.Max(best, 2 * open);
            else if (open > close)
                open = close = 0;
        }

        return best;
    }
}

Was this solution helpful?