Longest Valid Parentheses

November 24,2023

problem link: https://leetcode.com/problems/longest-valid-parentheses/

Typically, in the parentheses problem a stack is the obvious choice. I spent too much time, chasing a phantom solution by thinking about this as a DP problem and filling various arrays.

But, then This is similar to having a stack of positions of the previous ( positions and then just, popping them off when we encounter a ) and also maintaining a max value, with the difference between the current position and the top of the stack.

We keep track of the last valid position, by pushing -1 to the stack initially. if we reach the bottom, we do a stk.empty() check and then push the current position to the stack. This makes sure that, we are the latest valid position, when we encounter a ).

#include <stack>

using namespace std;

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

        for (int i = 0; i<n;i++){
            if (s[i] == '('){
                stk.push(i);
            }else {
                stk.pop();
                if (stk.empty()){
                    stk.push(i);
                }else {
                    ans = max(ans, i - stk.top());
                }
            }
        }

    }
};