A one pass O(n) time & space DP/stack solution easy to understand


  • 0
    Z
    class Solution {
    public:
        
        int longestValidParentheses(string s) {
            vector<int> stk;
            vector<int> max_len_vec(s.size(), 0);
            int max_len = 0; int len = 0;
            for(int i = 0; i < s.size(); ++i){
                if(s[i] == '('){
                    stk.push_back(i);
                }
                else{
                    if(stk.size() > 0){
                        int top = stk[stk.size() - 1];
                        stk.pop_back();
                        max_len_vec[i] =  i - top + 1 + max_len_vec[top-1];
                        if(max_len_vec[i] > max_len){
                            max_len = max_len_vec[i];
                        }
                    }
                }
            }
            return max_len;
        }
    };

Log in to reply
 

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