Question

Formatted question description: https://leetcode.ca/all/32.html

32	Longest Valid Parentheses

Given a string containing just the characters '(' and ')',
find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

@tag-stack

Algorithm

To solve with the help of the stack, you need to define a start variable to record the starting position of the valid bracket string.

Traverse the string,

  • if it encounters a left bracket, push the current index onto the stack,
  • if it encounters a right bracket,
    • if the current stack is empty, the next index position is recorded to be start,
    • if the stack is not empty, the top element of the stack is taken out, at this time,
      • if the stack is empty, update the result and the larger value of i-start + 1,
      • otherwise update the result and i-the greater value in st.top()

Code

Java

  • 
    public class Longest_Valid_Parentheses {
    
        class Solution_noExtraSpace {
            public int longestValidParentheses(String s) {
                int res = 0, left = 0, right = 0, n = s.length();
    
                // from left to right, '(()' => will never hit left==right
                for (int i = 0; i < n; ++i) {
                    if (s.charAt(i) == '(') ++left;
                    else ++right;
    
                    if (left == right) res = Math.max(res, 2 * right);
                    else if (right > left) left = right = 0;
                }
    
                // from right to left, '())' => will never hit left==right
                left = right = 0;
                for (int i = n - 1; i >= 0; --i) {
                    if (s.charAt(i) == '(') ++left;
                    else ++right;
    
                    if (left == right) res = Math.max(res, 2 * left);
                    else if (left > right) left = right = 0;
                }
                return res;
    
            }
        }
    
        class Solution_stack {
            public int longestValidParentheses(String s) {
                Stack<Integer> sk = new Stack<>();
                int start = 0;
                int result = 0;
                for (int i = 0;i < s.length(); i++) {
                    if(s.charAt(i) == '(') {
                        sk.push(i);
                    } else {
                        if (sk.empty()) {
                            start = i + 1;
                        } else {
                            sk.pop();
                            result = Math.max(result, sk.isEmpty() ? i - start + 1 : i - sk.peek());
                        }
                    }
                }
                return result;
    
            }
        }
    
        // @note: scan direction: right pointer from start to end, left pointer from right pointer to start
        public class Solution_start_to_end {
    
            public int longestValidParentheses(String s) {
    
                if (s == null || s.length() == 0) {
                    return 0;
                }
    
                int longest = 0;
                int j = 1;
    
                // this map will mark, from index=0 to position x, longest so far
                // 注意,这里是保证 s[i][j]是连续的valid,所以才可以用 "i = j - skipLeft - 1;"来找左边的 '('
                int[] longestSoFar = new int[s.length()];
    
                while(j < s.length()) {
    
                    int skipLeft = longestSoFar[j - 1];
                    int i = j - skipLeft - 1; // to find left "("
    
                    // @note: I missed boundary check for i
                    // if (s.charAt(i) == '(' && s.charAt(j) == ')') {
                    if (i >= 0 && s.charAt(i) == '(' && s.charAt(j) == ')') {
    
                        longestSoFar[j] = j - i + 1; // @note: or, longestSoFar[j - 1] += 2;
                        // System.out.println(i + " " + j);
    
                        // probe previous valid segement
                        if (i - 1 >= 0 && longestSoFar[i - 1] > 0) {
                            longestSoFar[j] += longestSoFar[i - 1];
                        }
    
                        longest = Math.max(longest, longestSoFar[j]);
                    }
    
                    j++;
                }
    
                return longest;
            }
        }
    
    
        // @note: scan direction: left pointer from end to start, right pointer from left pointer to end
        public class Solution_end_to_start {
            public int longestValidParentheses(String s) {
    
                if (s == null || s.length() == 0)   return 0;
    
                // 注意,这里是保证 s[i][j]是连续的valid,所以才可以用 "j = i + skip + 1;"来找右边的 '('
                int[] dp = new int[s.length()];
                int max = 0;
    
                // scan from end to start
                for (int i = s.length() - 2; i >= 0; i--) {
    
                    // check how many to skip
                    int skip = dp[i + 1];
                    int j = i + skip + 1;
    
                    // @note: i missed boundray check for j
                    if (j > s.length() - 1) {
                        continue;
                    }
    
                    if (s.charAt(i) == '(' && s.charAt(j) == ')') {
                        dp[i] = dp[i + 1] + 2;
    
                        // check position after j, eg: ))((()))()()((
                        if (j + 1 < s.length() && dp[j + 1] > 0)
                            dp[i] += dp[j + 1];
    
                        max = max > dp[i] ? max : dp[i];
                    }
                }
    
                return max;
            }
        }
    
    
        // @note: 2-d dp array, over time
        public int longestValidParentheses(String s) {
    
            if (s == null || s.length() == 0) {
                return 0;
            }
    
            int longest = Integer.MIN_VALUE;
            int j = 0;
    
            // marking, from i to j is valid parenthesis
            boolean[][] dp = new boolean[s.length()][s.length()];
    
            // @note: eg. ")()())", need another map to record previous longest valid
            // this map will mark, at position x, longest so far
            int[] longestSoFar = new int[s.length()];
    
            while(j < s.length()) {
    
                int i = 0;
                while(i <= j) {
    
                    // check if valid
                    if ((s.charAt(i) == '(' && s.charAt(j) == ')') && (j - i <= 1 || dp[i + 1][j - 1])) {
    
                        dp[i][j] = true;
                        // System.out.println(i + " " + j);
    
                        // probe previous valid segement
                        int prev = i > 0 ? longestSoFar[i - 1] : 0;
    
                        // check longest
                        longest = Math.max(longest, j - i + 1 + prev);
    
                        // @note: record longest so far
                        longestSoFar[j] = longest;
                    }
    
                    i++;
                }
    
                j++;
            }
    
            return longest;
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/longest-valid-parentheses/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        int longestValidParentheses(string s) {
            vector<int> dp(s.size() + 1, 0);
            int ans = 0;
            for (int i = 0; i < s.size(); ++i) {
                if (s[i] == '(') continue;
                int start = i - dp[i] - 1;
                if (start >= 0 && s[start] == '(')
                    dp[i + 1] = dp[i] + 2 + dp[start];
                ans = max(ans, dp[i + 1]);
            }
            return ans;
        }
    };
    
  • class Solution(object):
      def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        dp = [0 for _ in range(0, len(s))]
        left = 0
        ans = 0
        for i in range(0, len(s)):
          if s[i] == "(":
            left += 1
          elif left > 0:
            left -= 1
            dp[i] = dp[i - 1] + 2
            j = i - dp[i]
            if j >= 0:
              dp[i] += dp[j]
            ans = max(ans, dp[i])
        return ans
    
    

All Problems

All Solutions