Longest Valid Parentheses

Intuitionwhy one boundary index is enough to measure every valid region

A valid substring cannot cross an unmatched closing parenthesis. Once a closing parenthesis has nothing to match, every substring ending at or before that position is separated from anything after it, so that index becomes a new boundary. Between boundaries, unmatched opening parentheses are the only information that still matters.

Store indices of unmatched opening parentheses, with one extra boundary index at the bottom of the stack. For a closing parenthesis, remove one possible opening match. If an opening remains below it, the valid substring starts just after that index, so its length is the current index minus the stack top. If no opening remains, the close is unmatched and its own index becomes the next boundary.

Approach

1. 1Create a stack of indices and push -1 before scanning, because a valid substring that starts at index 0 needs a boundary just before the string.
2. 2For every opening parenthesis, push its index, because it may be the unmatched opening that limits a future valid suffix.
3. 3For every closing parenthesis, pop once to match it with the most recent unmatched opening; treating the close as a match attempt keeps the stack aligned with the parentheses seen so far.
4. 4If the pop empties the stack, push the current index as the new boundary, because this closing parenthesis is unmatched and no valid substring can cross it.
5. 5Otherwise, compute i - st.top(), because every character after the boundary at st.top() belongs to the current valid suffix ending at i.
6. 6Update the answer with that length and continue scanning, because a later region may be longer even though the current suffix is already valid.

Complexitythe scan is linear, but the stack can hold every opening parenthesis

Annotated solutionC++ · index stack · the boundary invariant in one pass

#include <algorithm>
#include <stack>
#include <string>

using namespace std;

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);
        int ans = 0;

        for (int i = 0; i < static_cast<int>(s.size()); ++i) {
            if (s[i] == '(') {
                st.push(i);
            } else {
                st.pop();

                if (st.empty()) {
                    st.push(i);
                } else {
                    ans = max(ans, i - st.top());
                }
            }
        }

        return ans;
    }
};

The sentinel -1 is not a parenthesis; it is a virtual position before the string. That makes i - st.top() equal to the correct length when a valid substring starts at index 0. The empty-stack branch is equally important: after an unmatched close, pushing i prevents later valid characters from being measured across that invalid position.

The dynamic programming alternativea different arrangement with the same time bound and more stored state

Dynamic programming can store the length of the longest valid substring that ends exactly at each index. A closing parenthesis can extend the valid suffix ending at i - 1, then possibly join the valid block before its matching opening parenthesis. This avoids an explicit stack, but dp stores one value per character, so it is not a space optimisation; it is a different arrangement of the same linear scan.

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = static_cast<int>(s.size());
        vector<int> dp(n, 0);
        int ans = 0;

        for (int i = 1; i < n; ++i) {
            if (s[i] != ')') {
                continue;
            }

            int opening = i - dp[i - 1] - 1;
            if (opening >= 0 && s[opening] == '(') {
                dp[i] = dp[i - 1] + 2;
                if (opening > 0) {
                    dp[i] += dp[opening - 1];
                }
                ans = max(ans, dp[i]);
            }
        }

        return ans;
    }
};

Common mistakesthree wrong shapes that produce plausible but incorrect scans