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 "()()"
题意：
给定一个括号序列，找出最长的合法括号子串。
Solution1: Two pointers(fast&slow) + Stack
It's just like using [start+1...i] to maintain a window where contains longest valid parentheses
code:
/*
Time: O(n). We traverse the given input
Space: O(n). Worse case, input is all contained '（'， then there will be n chars stored in the stack
*/
class Solution {
public int longestValidParentheses(String s) {
int result = 0;
int start = -1;
Stack<Integer> stack = new Stack<>(); // index of every char for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(c == '('){
stack.push(i);
}else if( c == ')'){
if(stack.isEmpty()){
// no matching left '( '
start = i;
}else{
stack.pop();
if(stack.isEmpty()){
result = Math.max(result, i - start);
}else{
result = Math.max(result, i - stack.peek());
}
}
}
}
return result;
}
}