32. Longest Valid Parentheses

Time: O(n)

Space: O(n)

Intuition

Use a stack to track indices of unmatched characters. Push -1 as a base sentinel. When ")" is seen and the stack top is a "(" index, pop it (they form a matched pair) and the current valid length is i - stack.Peek(). If the stack becomes empty, push i as the new base.

Algorithm

1Push -1 onto stack as base.
2For each index i: if s[i] == "(", push i.
3Else (s[i] == ")"): pop from stack. If stack is empty, push i as new base. Else update maxLen = max(maxLen, i - stack.Peek()).
4Return maxLen.

Example Walkthrough

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

1.i=0 ")" : pop -1 -> empty. Push 0 as base.
2.i=1 "(" : push 1. i=2 ")" : pop 1. Stack=[0]. len=2-0=2.
3.i=3 "(" : push 3. i=4 ")" : pop 3. Stack=[0]. len=4-0=4.
4.i=5 ")" : pop 0 -> empty. Push 5 as base.
5.maxLen=4.

Output: 4

Common Pitfalls

•The base sentinel (-1 or the index of an unmatched ")") is critical for correct length calculation.

32.cs

// Approach: DP where dp[i] = length of the longest valid parentheses string ending at index i.
// If s[i] == ')' and s[i-1] == '(': dp[i] = dp[i-2] + 2 (direct match with immediate predecessor).
// If s[i] == ')' and s[i-1] == ')': check the char at i - dp[i-1] - 1.
//   If it is '(', then dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2] (extend through the prior valid run).
// The answer is the maximum dp value.
// Prepend ')' to avoid out-of-bounds indexing at position 0.
// Time: O(n) Space: O(n) for the dp array.

public class Solution
{
    public int LongestValidParentheses(string s)
    {
        string s2 = ")" + s;
        // dp[i] := the length of the longest valid parentheses in the substring
        // s2[1..i]
        int[] dp = new int[s2.Length];

        for (int i = 1; i < s2.Length; ++i)
        {
            if (s2[i] == ')' && s2[i - dp[i - 1] - 1] == '(')
                dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
        }

        return dp.Max();
    }
}

Was this solution helpful?