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

• Java
• C++
• Python
• Go
• C#
• TypeScript
• Javascript

• 
  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