Day 55 #32, Longest Valid Parentheses

Longest Valid Parentheses
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
--------------------------------------------------------------
COME_BACK
DP
dp[i] contains the value of the longest valid parentheses that starts at index i to the end of string s. It is zero if s[i] == ')' or if the corresponding s[j] == '('

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> dp(s.length() + 1,0);
        int longest = 0;
        
        for (int i = s.length() - 2; i >= 0; i--) {
            if (s[i] == ')') continue;
            int farRight = i + 1 + dp[i + 1];
            if (s[farRight] == ')') dp[i] = 2 + dp[i + 1] + dp[farRight + 1];
            longest = max(longest,dp[i]);
        }
        
        return longest;
    }
};

Solution #2, from internet, stack contains the parentheses whose indexes could not be matched.

The workflow of the solution is as below.

1. Scan the string from beginning to end.
2. If current character is '(', push its index to the stack. If current character is ')' and the character at the index of the top of stack is '(', we just find a matching pair so pop from the stack. Otherwise, we push the index of ')' to the stack.
3. After the scan is done, the stack will only contain the indices of characters which cannot be matched. Then let's use the opposite side - substring between adjacent indices should be valid parentheses.
4. If the stack is empty, the whole input string is valid. Otherwise, we can scan the stack to get longest valid substring as described in step 3.

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length(), longest = 0;
        stack<int> st;
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') st.push(i);
            else {
                if (!st.empty()) {
                    if (s[st.top()] == '(') st.pop();
                    else st.push(i);
                }
                else st.push(i);
            }
        }
        if (st.empty()) longest = n;
        else {
            int a = n, b = 0;
            while (!st.empty()) {
                b = st.top(); st.pop();
                longest = max(longest, a-b-1);
                a = b;
            }
            longest = max(longest, a);
        }
        return longest;
    }
};

Updated on Oct-30th-2014
Mine

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                st.push(i);
            }else if (s[i] == ')'){
                // found a match
                if (!st.empty() && s[st.top()] == '(') {
                    st.pop();
                } // not found
                else {
                    st.push(i);
                }
            }
            
        }
        // the whole string is valid
        if (st.empty()) return s.length();
        
        int first = s.length();        
        int longest = 0;
        while (!st.empty()) {
            int cur = st.top();
            st.pop();
            longest = max(longest,first - cur - 1);
            first = cur;
        }
        
        // for cases that have valid parentheses at the beginning
        if (first != 0) {
            longest = max(longest,first - 0);
        }
        
        return longest;
    }
};

Updated on Oct-30th-2014
refactoried of previous solutio, setup two sentinels indicating the beginning and end of string

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ')' && st.size() > 1 && s[st.top()] == '(') {
                st.pop();
            }else {
                st.push(i);
            }
        }

        st.push(s.length());
        int longest = 0;
        while (st.size() > 1) {
            int cur = st.top();
            st.pop();
            longest = max(longest,cur - st.top() - 1);
        }
        
        return longest;
    }
};

Java, updated on Aug-26th-2018
Solution #1 DP,
ToDo, 这题2个方法都要死记

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        int longest = 0;
        
        for (int i = n - 2; i >= 0; i--) {
            if (s.charAt(i) == ')') continue;
            int farRight = i + dp[i + 1] + 1;
            if (farRight < n && s.charAt(farRight) == ')') {
                dp[i] = dp[i + 1] + 2 + dp[farRight + 1];
                longest = Math.max(dp[i], longest);
            }
        }
        
        return longest;
    }
}

Solution #2, stack

class Solution {
        
    public int longestValidParentheses(String s) {
        Stack stC = new Stack<>();
        Stack stI = new Stack<>();
        stI.add(-1);
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!stC.isEmpty() && c == ')' && stC.peek() == '(') {
                stC.pop();
                stI.pop();
            }else {
                stC.add(c);
                stI.add(i);
            }
        }
        
        int longest = 0;
        int cur = s.length();
        while (!stI.isEmpty()) {
            int i = stI.pop();
            longest = Math.max(longest, cur - i - 1);
            cur = i;
        }
        
        return Math.max(0, longest);
    }
}

Solution #3 简单到爆。WOW!!!
考虑"(()" ，光走第一个loop不会得到结果
再考虑"(()(()"，中途抵消掉时增加长度也不会得到正确结果

class Solution {
    public int longestValidParentheses(String s) {
        int longest = 0;
        int left = 0, right = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                left++;
            }else {
                right++;
            }
            
            if (left == right) longest = Math.max(longest, left + right);
            else if (right > left) {
                right = 0;
                left = 0;
            }
        }
        
        left = 0;
        right = 0;
        
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == '(') {
                left++;
            }else {
                right++;
            }
            
            if (left == right) longest = Math.max(longest, left + right);
            else if (left > right) {
                right = 0;
                left = 0;
            }
        }
        
        return longest;
    }
}