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()
- if the stack is empty, update the result and the larger value of
- if the current stack is empty, the next index position is recorded to be
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); };