Simple stack C++ with explanation


  • 0
    M

    Basic idea is to push the invalid indexes in stack, and everytime you find the match pop out one pair. The longest string seen so far will be the current index - the index remaining on stack.

     int longestValidParentheses(string s) {
            stack <int> S;
            
            int maxlen = 0;
            
            for (int i = 0; i < s.length(); i++) {
                if (S.empty()) {
                    S.push(i);
                } else if (s[i] == ')' && s[S.top()] == '(') {
                    S.pop();
                    int l = S.empty() ? i + 1 : i - S.top();
                    maxlen = max(maxlen, l);
                } else {
                    S.push(i);
                }
            }
            
            return maxlen;
        }
    

Log in to reply
 

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