O(n), easy to understand


  • 0
    H

    The idea is to decide the boundaries of valid substrings. We scan the string twice, once from the left, and once from the right. Each time we use a stack to keep track the current open brackets ('(' for from-left and ')' for from-right). Once we encounter a close bracket (')' for from-left and '(' for from-right) if the stack is empty, then the current position is a boundary. We mark all the boundaries and then the length of the longest substring without crossing the boundary is the answer.

    void fromleft(string s, char open, vector<bool>& seg) {
        stack<char> st;
        for (int i = 0; i < s.length(); i ++) {
            if (s[i] == open)
                st.push(s[i]);
            else {
                if (st.empty()) {
                    int idx = i;
                    if (open == ')')
                        idx = s.length()-idx-1;
                    seg[idx] = true;
                }
                else st.pop();
            }
        }
    }
    
    class Solution {
    public:
        int longestValidParentheses(string s) {
            vector<bool> seg(s.length());
            string sr = s;
            reverse(sr.begin(), sr.end());
            fromleft(s, '(', seg);
            fromleft(sr, ')', seg);
            
            int cur = 0, max_len = 0;
            for (int i = 0; i < s.length(); i ++) {
                if (seg[i]) {
                    max_len = max(max_len, cur);
                    cur = 0;
                }
                else
                    cur ++;
            }
            max_len = max(max_len, cur);
            return max_len;
        }
    };

Log in to reply
 

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