Welcome to Subscribe On Youtube

Question

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

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

 

Example 1:

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

Example 2:

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

Example 3:

Input: s = ""
Output: 0

 

Constraints:

  • 0 <= s.length <= 3 * 104
  • s[i] is '(', or ')'.

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

  • 
    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;
        }
    
    }
    
    ############
    
    class Solution {
        public int longestValidParentheses(String s) {
            int n = s.length();
            if (n < 2) {
                return 0;
            }
            char[] cs = s.toCharArray();
            int[] dp = new int[n];
            int ans = 0;
            for (int i = 1; i < n; ++i) {
                if (cs[i] == ')') {
                    if (cs[i - 1] == '(') {
                        dp[i] = 2 + (i > 1 ? dp[i - 2] : 0);
                    } else {
                        int j = i - dp[i - 1] - 1;
                        if (j >= 0 && cs[j] == '(') {
                            dp[i] = 2 + dp[i - 1] + (j > 0 ? dp[j - 1] : 0);
                        }
                    }
                    ans = Math.max(ans, dp[i]);
                }
            }
            return ans;
        }
    }
    
  • // 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:
        def longestValidParentheses(self, s: str) -> int:
            left = right = 0
            res = 0
            for c in s: # from left to right, '(()' => will never hit left==right
                if c == '(':
                    left += 1
                else:
                    right += 1
                if left == right:
                    res = max(res, 2 * left)
                if left < right:
                    left = right = 0
    
            left = right = 0 # dont forget to reset
            for c in reversed(s): # from right to left, '())' => will never hit left==right
                if c == '(':
                    left += 1
                else:
                    right += 1
                if left == right:
                    res = max(res, 2 * left)
                if left > right: # reverse '<' to '>'
                    left = right = 0
    
            return res
    
    class Solution:
        def longestValidParentheses(self, s: str) -> int:
            n = len(s)
            if n < 2:
                return 0
            dp = [0] * n
            for i in range(1, n):
                if s[i] == ')':
                    if s[i - 1] == '(':
                        dp[i] = 2 + (dp[i - 2] if i > 1 else 0)
                    else:
                        j = i - dp[i - 1] - 1
                        if j >= 0 and s[j] == '(':
                            dp[i] = 2 + dp[i - 1] + dp[j - 1]
            return max(dp)
    
    ############
    
    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
    
    
  • func longestValidParentheses(s string) int {
    	n := len(s)
    	if n < 2 {
    		return 0
    	}
    	dp := make([]int, n)
    	ans := 0
    	for i := 1; i < n; i++ {
    		if s[i] == ')' {
    			if s[i-1] == '(' {
    				dp[i] = 2
    				if i > 1 {
    					dp[i] += dp[i-2]
    				}
    			} else {
    				j := i - dp[i-1] - 1
    				if j >= 0 && s[j] == '(' {
    					dp[i] = 2 + dp[i-1]
    					if j > 0 {
    						dp[i] += dp[j-1]
    					}
    				}
    			}
    			ans = max(ans, dp[i])
    		}
    	}
    	return ans
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
  • using System.Collections.Generic;
    
    public class Solution {
        public int LongestValidParentheses(string s) {
            var result = 0;
            var baseCount = 0;
            var stack = new Stack<int>();
            foreach (var ch in s)
            {
                switch (ch)
                {
                    case '(':
                        stack.Push(1);
                        break;
                    case ')':
                        if (stack.Count > 0)
                        {
                            var count = stack.Pop() + 1;
                            if (stack.Count > 0)
                            {
                                count += stack.Pop();
                                stack.Push(count);
                                if (count - 1 > result) result = count - 1;
                            }
                            else
                            {
                                baseCount += count;
                                if (baseCount > result) result = baseCount;
                            }
                        }
                        else
                        {
                            baseCount = 0;
                        }
                        break;
                }
            }
            return result;
        }
    }
    
  • function longestValidParentheses(s: string): number {
        const n = s.length;
        const f: number[] = new Array(n + 1).fill(0);
        for (let i = 2; i <= n; ++i) {
            if (s[i - 1] === ')') {
                if (s[i - 2] === '(') {
                    f[i] = f[i - 2] + 2;
                } else {
                    const j = i - f[i - 1] - 1;
                    if (j && s[j - 1] === '(') {
                        f[i] = f[i - 1] + 2 + f[j - 1];
                    }
                }
            }
        }
        return Math.max(...f);
    }
    
    
  • /**
     * @param {string} s
     * @return {number}
     */
    var longestValidParentheses = function (s) {
        const n = s.length;
        const f = new Array(n + 1).fill(0);
        for (let i = 2; i <= n; ++i) {
            if (s[i - 1] === ')') {
                if (s[i - 2] === '(') {
                    f[i] = f[i - 2] + 2;
                } else {
                    const j = i - f[i - 1] - 1;
                    if (j && s[j - 1] === '(') {
                        f[i] = f[i - 1] + 2 + f[j - 1];
                    }
                }
            }
        }
        return Math.max(...f);
    };
    
    

All Problems

All Solutions