O(n) solution using stack. No DP.


  • 0
    S

    '''

    class Solution {
    public:
    int longestValidParentheses(string s) {
        int i=0, l=s.size(), res=0,count=0;
        vector<bool>mark(l,false); //to mark the index of valid parenthesis
        stack<int> index;
        while(i<l){
            if(s[i]=='(') index.push(i);
            else if(index.size()){
                mark[i]=true;
                mark[index.top()]=true;
                index.pop();
            }
            i++;
        }
        //to find the longest substring of valid parenthesis
        for(i=0;i<l;i++){
            if(mark[i]){
                count++;
                res = max(res, count);
            }
            else count=0;
        }
        return res;
    }
    

    };

    '''


Log in to reply
 

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