• ㊗️
• 大家
• offer
• 多多！

Problem

Given a string containing just the characters ‘(‘ and ‘)’, find 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 * 10^4$
• s[i] is ‘(‘, or ‘)’.

Code

) ( ) ( ) )
0 1 2 3 4 5

class Solution {
public int longestValidParentheses(String s) {
int res = 0;
// push index
Stack<Integer> stack = new Stack<>();
stack.push(-1);

for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);

if(c == '('){
stack.push(i);
} else {
stack.pop();
if(stack.isEmpty()){
stack.push(i);
} else {
res = Math.max(res, i - stack.peek());
}
}
}

return res;
}
}


class Solution {
public int longestValidParentheses(String s) {
int left = 0, right = 0, maxLen = 0;

for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}

if (left == right) {
maxLen = Math.max(maxLen, 2 * right);
} else if (right > left) {
left = right = 0;
}
}

left = right = 0;

for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}

if (left == right) {
maxLen = Math.max(maxLen, 2 * left);
} else if (left > right) {
left = right = 0;
}
}
return maxLen;
}
}