C++ 1-pass solution using stack, with comments.


  • 0
    A
    class Solution {
    public:
        int longestValidParentheses(string s) {
            /*
              For each open paranthesis, the stack stores the index from where a valid run would start
              if we were to close that paranthesis in a valid manner. i.e. for example, in
              (()(
              the top of the stack would read 1, since, if we manage to find a valid run that closes the
              last open paren, we would have a valid run starting from 1 up to wherever we close that paren.
              Whereas, in
              (()((
              the top of the stack would read 3, since if we close that paren, we would have a valid run
              starting from index 3 up to the paren that matches it.
             */
            std::stack<int> validStartStack;
            
            /*
              This variable stores the index from which we have a valid run at present. For example, if we had
              )((()()()
              this variable would store 3, because we have a valid run starting from index 3. Whereas, if we had
              )((()()()(
              it would be set to -1 because we are not seeing a valid run
             */
            int lastValidStart = -1;
            
            int maxLength = 0;
            int i = 0;
            for( ; i < s.length(); ++i ) {
                if( s[i] == '(' ) {
                    validStartStack.push( lastValidStart < 0 ? i : lastValidStart );
                    lastValidStart = -1;
                }
                else {
                    if( validStartStack.empty() ) {
                        lastValidStart = -1;
                        continue;
                    }
                    lastValidStart = validStartStack.top();
                    int length = i - lastValidStart + 1;
                    if( length > maxLength )
                        maxLength = length;
                    validStartStack.pop();
                }
            }
            return maxLength;
        }
    };
    

Log in to reply
 

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