Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length = 2. Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
X. Using stack
Scan the string from beginning to end.
If current character is '(',
push its index to the stack. If current character is ')' and the
character at the index of the top of stack is '(', we just find a
matching pair so pop from the stack. Otherwise, we push the index of
')' to the stack.
After the scan is done, the stack will only
contain the indices of characters which cannot be matched. Then
let's use the opposite side - substring between adjacent indices
should be valid parentheses.
If the stack is empty, the whole input
string is valid. Otherwise, we can scan the stack to get longest
valid substring as described in step 3.
第二：消除掉')'之后，栈内没有剩余的‘(’了。此时需要引入一个新的变量start，用于表示合法括号字符串的起点。
例如：对于这种情况：())()()，可以正确的得出最大值为4。
start初始为-1，之后每次碰到‘)’且栈为空的时候更新为当前‘)’的index。也就是说无法消除的)之后的括号不可能再和前面的括号合并在一起计算最长序列，所以更新start。
https://www.jianshu.com/p/72a4cecbf8c7
https://leetcode.com/problems/longest-valid-parentheses/discuss/14133/my-dp-on-solution-without-using-stack
DP, Code from http://www.darrensunny.me/leetcode-longest-valid-parentheses/
int n = s.length();
int[] dp = new int[n];
java.util.Arrays.fill(dp, 0);
int max = 0;
for (int i = n - 2; i >= 0; i--) {
if (s.charAt(i) == '(') {
int j = i + 1 + dp[i + 1];
if (j < n && s.charAt(j) == ')') {
dp[i] = dp[i + 1] + 2;
int k = 0;
if (j + 1 < n) {
k = dp[j + 1];
}
dp[i] += k;
}
max = Math.max(max, dp[i]);
}
}
return max;
}
https://leetcode.com/articles/longest-valid-parentheses/
Better solution – O(1) Constant Space Solution
a string becomes invalid for the first unmatched ‘)’ or the last unmatched
O(n) time and O(n) space
X. https://leetcode.com/articles/longest-valid-parentheses/
Time complexity : . Generating every possible substring from a string of length requires . Checking validity of a string of length requires .
X. Using stack
https://www.jianshu.com/p/392b9058f503
https://discuss.leetcode.com/topic/2289/my-o-n-solution-using-a-stack/2
public int longestValidParentheses(String s) {
LinkedList<Integer> stack = new LinkedList<>();
int result = 0;
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ')' && stack.size() > 1 && s.charAt(stack.peek()) == '(') {
stack.pop();
result = Math.max(result, i - stack.peek());
} else {
stack.push(i);
}
}
return result;
}
}push its index to the stack. If current character is ')' and the
character at the index of the top of stack is '(', we just find a
matching pair so pop from the stack. Otherwise, we push the index of
')' to the stack.
contain the indices of characters which cannot be matched. Then
let's use the opposite side - substring between adjacent indices
should be valid parentheses.
string is valid. Otherwise, we can scan the stack to get longest
valid substring as described in step 3.
int longestValidParentheses(string s) {
int n = s.length(), longest = 0;
stack<int> st;
for (int i = 0; i < n; i++) {
if (s[i] == '(') st.push(i);
else {
if (!st.empty()) {
if (s[st.top()] == '(') st.pop();
else st.push(i);
}
else st.push(i);
}
}
if (st.empty()) longest = n;
else {
int a = n, b = 0;
while (!st.empty()) {
b = st.top(); st.pop();
longest = max(longest, a-b-1);
a = b;
}
longest = max(longest, a);
}
return longest;
}
http://www.cnblogs.com/grandyang/p/4424731.html
这里我们还是借助栈来求解，需要定义个start变量来记录合法括号串的起始位置，我们遍历字符串，如果遇到左括号，则将当前下标压入栈，如果遇到右括号，如果当前栈为空，则将下一个坐标位置记录到start，如果栈不为空，则将栈顶元素取出，此时若栈为空，则更新结果和i - start + 1中的较大值，否则更新结果和i - 栈顶元素中的较大值
https://zxi.mytechroad.com/blog/stack/leetcode-32-longest-valid-parentheses/
这里我们还是借助栈来求解，需要定义个start变量来记录合法括号串的起始位置，我们遍历字符串，如果遇到左括号，则将当前下标压入栈，如果遇到右括号，如果当前栈为空，则将下一个坐标位置记录到start，如果栈不为空，则将栈顶元素取出，此时若栈为空，则更新结果和i - start + 1中的较大值，否则更新结果和i - 栈顶元素中的较大值
https://zxi.mytechroad.com/blog/stack/leetcode-32-longest-valid-parentheses/
int longestValidParentheses(string s) {
stack<int> q;
int start = 0;
int ans = 0;
for (int i = 0;i < s.length(); i++) {
if(s[i] == '(') {
q.push(i);
} else {
if (q.empty()) {
start = i + 1;
} else {
int index = q.top(); q.pop();
ans = max(ans, q.empty() ? i - start + 1 : i - q.top());
}
}
}
return ans;
}
The idea is simple, we only update the result (max) when we find a "pair".
If we find a pair. We throw this pair away and see how big the gap is between current and previous invalid.
EX: "( )( )"
stack: -1, 0,
when we get to index 1 ")", the peek is "(" so we pop it out and see what's before "(".
In this example it's -1. So the gap is "current_index" - (-1) = 2.
The idea only update the result (max) when we find a "pair" and push -1 to stack first covered all edge cases.
If we find a pair. We throw this pair away and see how big the gap is between current and previous invalid.
EX: "( )( )"
stack: -1, 0,
when we get to index 1 ")", the peek is "(" so we pop it out and see what's before "(".
In this example it's -1. So the gap is "current_index" - (-1) = 2.
The idea only update the result (max) when we find a "pair" and push -1 to stack first covered all edge cases.
Since any valid parentheses sequence starts from a '(' and ends at ')', we can calculate new length when we meet a ')'. The key is to use a stack to store all the indices and the start position is always the one on top of the stack. See the code below for details.
// Using a stack. One pass
int longestValidParentheses(string s) {
vector<int> stack;
int maxLen = 0;
for (int i = 0; i < s.size(); ++i)
{
if (s[i] == '(')
stack.push_back(i);
else {
if (!stack.empty() && s[stack.back()] == '(') {
stack.pop_back();
int lastPos = -1;
if (!stack.empty())
lastPos = stack.back();
int curLen = i - lastPos;
maxLen = (maxLen < curLen) ? curLen : maxLen;
} else
stack.push_back(i);
}
}
return maxLen;
}- stack里面装的一直是“还没配好对的那些可怜的括号的index”
- 是'(‘的时候push
- 是’)’的时候，说明可能配对了；看stack top是不是左括号，不是的话，push当前右括号
- 是的话，pop那个配对的左括号，然后update res：i和top的（最后一个配不成对的）index相减，就是i属于的这一段的当前最长。如果一pop就整个栈空了，说明前面全配好对了，那res就是最大=i+1
public int longestValidParentheses(String s) {
int res = 0;
Stack<Integer> stack = new Stack<Integer>();
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == ')' && !stack.isEmpty() && arr[stack.peek()] == '(') {
stack.pop();
if (stack.isEmpty())
res = i + 1;
else
res = Math.max(res, i - stack.peek());
} else {
stack.push(i);
}
}
return res;
}
解题思路：最容易想到的解法就是穷举法，计算任意两点(i到j)之间有多少个合法的()串，借助动态规划可以得到结果。算法复杂度为：O(n3)
想要O(n)的解法需要一点技巧，栈中保存的不是‘(’而是‘(’所在的index，在此基础上也要弄清楚几种情况：
每次来了‘(’之后，无条件压栈。如果碰到')'的话，如果栈不为空，就消除栈内剩余的'('
第一：消除掉'('之后，如果栈内还有剩余的‘(’的话，最长的合法长度就是：maxLength = Math.max(i - (int)stack.peek() , maxLength); 也就是取：当前')'的index减去栈顶元素的index 和 原来max_length 两者的最大值。
想要O(n)的解法需要一点技巧，栈中保存的不是‘(’而是‘(’所在的index，在此基础上也要弄清楚几种情况：
每次来了‘(’之后，无条件压栈。如果碰到')'的话，如果栈不为空，就消除栈内剩余的'('
第一：消除掉'('之后，如果栈内还有剩余的‘(’的话，最长的合法长度就是：maxLength = Math.max(i - (int)stack.peek() , maxLength); 也就是取：当前')'的index减去栈顶元素的index 和 原来max_length 两者的最大值。
例如：对于这种情况：()(()()，可以正确的得出最大值为4。
第二：消除掉')'之后，栈内没有剩余的‘(’了。此时需要引入一个新的变量start，用于表示合法括号字符串的起点。
例如：对于这种情况：())()()，可以正确的得出最大值为4。
start初始为-1，之后每次碰到‘)’且栈为空的时候更新为当前‘)’的index。也就是说无法消除的)之后的括号不可能再和前面的括号合并在一起计算最长序列，所以更新start。
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0)
return 0;
int longestLength = 0; // Length of the longest valid parentheses
int start = 0; // The start index of the possibly longest valid parentheses
Stack<Integer> stack = new Stack<Integer>();
// One-pass scan
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') { // Opening parenthesis
stack.push(i); // Push its index
} else { // Closing parenthesis
if (stack.empty()) { // No opening parenthesis to match
start = i + 1; // i+1 is the start of next possibly LVP
} else {
stack.pop(); // The index of the opening parenthesis matched by s[i]
if (stack.empty()) // s[start...i] is matched
longestLength = Math.max(longestLength, i-start+1);
else // s[stack.peek()] is unmatched; s[stack.peek()+1...i] is matched
longestLength = Math.max(longestLength, i-stack.peek());
}
}
}
return longestLength;
}
This problem could be solved by linear scan as well. That is, maintain a stack, and scan the string from left to right, if it is ‘(‘, just push it (the index of this character) into the stack, if it is ‘)’, there are two cases, if the stack is NOT empty and the top is ‘(‘, then pop the stack out, get the current length of the valid sub string (current index - the top index in the stack after popping). Update the global maximum length if this length is larger. The second case (otherwise), we just push ‘)’ into the stack.
The key point here is that: when we encounter a ‘)’ at position B and pop out a matched ‘(‘ at position A, we know the string between S[A, B] must be a valid Parentheses. The following code implements this idea and is accepted by the LeetCode OJ to pass this Longest Valid Parentheses:
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
int len = 0;
int tmp = 0;
stack<int> stk;
for (int i = 0; i < n; ++i) {
if ('(' == s[i])
stk.push(i);
else {
if (!stk.empty() && '(' == s[stk.top()]) {
stk.pop();
tmp = i - (stk.empty() ? -1 : stk.top());
len = max(len, tmp);
}
else {
stk.push(i);
}
}
}
return len;
}
};
X. DPhttps://www.jianshu.com/p/72a4cecbf8c7
https://leetcode.com/problems/longest-valid-parentheses/discuss/14133/my-dp-on-solution-without-using-stack
I construct a array longest[], for any longest[i], it stores the longest length of valid parentheses which is end at i.
And the DP idea is :
If s[i] is '(', set longest[i] to 0,because any string end with '(' cannot be a valid one.
Else if s[i] is ')'
If s[i-1] is '(', longest[i] = longest[i-2] + 2
Else if s[i-1] is ')' and s[i-longest[i-1]-1] == '(', longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]
For example, input "()(())", at i = 5, longest array is [0,2,0,0,2,0], longest[5] = longest[4] + 2 + longest[1] = 6.
And the DP idea is :
If s[i] is '(', set longest[i] to 0,because any string end with '(' cannot be a valid one.
Else if s[i] is ')'
If s[i-1] is '(', longest[i] = longest[i-2] + 2
Else if s[i-1] is ')' and s[i-longest[i-1]-1] == '(', longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]
For example, input "()(())", at i = 5, longest array is [0,2,0,0,2,0], longest[5] = longest[4] + 2 + longest[1] = 6.
int longestValidParentheses(string s) {
if(s.length() <= 1) return 0;
int curMax = 0;
vector<int> longest(s.size(),0);
for(int i=1; i < s.length(); i++){
if(s[i] == ')'){
if(s[i-1] == '('){
longest[i] = (i-2) >= 0 ? (longest[i-2] + 2) : 2;
curMax = max(longest[i],curMax);
}
else{ // if s[i-1] == ')', combine the previous length.
if(i-longest[i-1]-1 >= 0 && s[i-longest[i-1]-1] == '('){
longest[i] = longest[i-1] + 2 + ((i-longest[i-1]-2 >= 0)?longest[i-longest[i-1]-2]:0);
curMax = max(longest[i],curMax);
}
}
}
//else if s[i] == '(', skip it, because longest[i] must be 0
}
return curMax;
}
括号题也不是只用stack才能做，这题是算长度，所以stack那种一match就俩一起pop了的方式就不适合了。求极值，一维dp最好使。
- d[i]: 以i开头的最长valid parentheses有多长。
- d[i] =
- if (str[i] == ‘)’)，以右括号开头必定invalid，d[i] = 0
- if (str[i] == ‘(‘)，以左括号开头
- 我们想看对应的有木有右括号。因为d[i + 1]代表的sequence肯定是左括号开头右括号结尾，所以我们想catch((…))这种情况。j = i + 1 + d[i + 1]，正好就是str[i]后面越过完整sequence的下一个，若是右括号，d[i] = 2 + d[i + 1]
- 除此之外，还有包起来后因为把后面的右括号用了而导致跟再往后也连起来了的情况，如((..))()()()。所以d[i]还要再加上j后面那一段的d[j + 1]
这个定义和最长公共字串那题的定义类似，都是“以某个固定位置开始/结束”。看两头的方式又像palindrome。从后往前的一维dp也不常见。挺好玩的，一下复习好多东西。
public int longestValidParentheses(String s) {
if (s.length() == 0)
return 0;
int maxLen = 0;
int[] d = new int[s.length()];
// d[i] means substring starts with i has max valid lenth of d[i]
d[s.length() - 1] = 0;
for (int i = s.length() - 2; i >= 0; i--) {
if (s.charAt(i) == ')')
d[i] = 0;
else {
int j = (i + 1) + d[i + 1];
if (j < s.length() && s.charAt(j) == ')') {
d[i] = d[i + 1] + 2; //(()())的外包情况
if (j + 1 < s.length())
d[i] += d[j + 1];//()()的后面还有的情况
}
}
maxLen = Math.max(maxLen, d[i]);
}
return maxLen;
}
这道题可以用一维动态规划逆向求解。假设输入括号表达式为String s，维护一个长度为s.length的一维数组dp[]，数组元素初始化为0。 dp[i]表示从s[i]到s[s.length - 1]最长的有效匹配括号子串长度。则存在如下关系：
- dp[s.length - 1] = 0;
- 从i - 2 -> 0逆向求dp[]，并记录其最大值。若s[i] == '('，则在s中从i开始到s.length - 1计算s[i]的值。这个计算分为两步，通过dp[i + 1]进行的（注意dp[i + 1]已经在上一步求解）：
- 在s中寻找从i + 1开始的有效括号匹配子串长度，即dp[i + 1]，跳过这段有效的括号子串，查看下一个字符，其下标为j = i + 1 + dp[i + 1]。若j没有越界，并且s[j] == ‘)’，则s[i ... j]为有效括号匹配，dp[i] =dp[i + 1] + 2。
- 在求得了s[i ... j]的有效匹配长度之后，若j + 1没有越界，则dp[i]的值还要加上从j + 1开始的最长有效匹配，即dp[j + 1]。
int n = s.length();
int[] dp = new int[n];
java.util.Arrays.fill(dp, 0);
int max = 0;
for (int i = n - 2; i >= 0; i--) {
if (s.charAt(i) == '(') {
int j = i + 1 + dp[i + 1];
if (j < n && s.charAt(j) == ')') {
dp[i] = dp[i + 1] + 2;
int k = 0;
if (j + 1 < n) {
k = dp[j + 1];
}
dp[i] += k;
}
max = Math.max(max, dp[i]);
}
}
return max;
}
维护一个s.length()一维数组，dp，其中dp[i]表示从索引i到末尾所组成字符串的前缀最长的有效括号组合的长度。
例如：)()，则为0，而非2；())()，为2，表示的是前面的()
因此：dp[s.length() - 1] = 0;从后向前逆向求解dp[i]，
- 如果s[i]=')'，则显然dp[i]=0;（均不合法）
- 如果s[i]='('，跳过dp[i+1]这段长度从j=i+1+dp[i+1]开始（找到最长前缀的后驱），如果j没越界并且s[j]=')'，正好和s[i]匹配（组成了dp[i]的合法最长前缀），则dp[i]=dp[i+1]+2；另外此时可能j之后的也可以连上，所以，可能要加上dp[j+1];
2 public int longestValidParentheses(String s) { 3 if(s == null || s.length() < 2) return 0; 4 int max = 0; 5 int[] dp = new int[s.length()]; 6 dp[s.length() - 1] = 0; 7 for(int i = s.length() - 2; i >= 0; i--){ 8 if(s.charAt(i) == '('){ 9 int j = i + 1 + dp[i + 1]; 10 if(j < s.length() && s.charAt(j) == ')'){ 11 dp[i] = dp[i + 1] + 2; 12 if(j + 1 < s.length()){ 13 dp[i] += dp[j + 1]; 14 } 15 } 16 } 17 max = Math.max(max,dp[i]); 18 } 19 return max; 20 }https://discuss.leetcode.com/topic/35776/two-java-solutions-with-explanation-stack-dp-short-easy-to-understand
The idea is go through the string and use DP to store the longest valid parentheses at that point.
take example "()(())"
i : [0,1,2,3,4,5]
s : [( ,) ,( ,( ,) ,) ]
DP:[0,2,0,0,2,6]
take example "()(())"
i : [0,1,2,3,4,5]
s : [( ,) ,( ,( ,) ,) ]
DP:[0,2,0,0,2,6]
1, We count all the ‘(‘.
2, If we find a ‘)’ and ‘(‘ counter is not 0, we have at least a valid result size of 2. “()"
3, Check the the one before (i - 1). If DP[i - 1] is not 0 means we have something like this “(())” . This will have DP “0024"
4, We might have something before "(())”. Take "()(())” example, Check the i = 1 because this might be a consecutive valid string.
2, If we find a ‘)’ and ‘(‘ counter is not 0, we have at least a valid result size of 2. “()"
3, Check the the one before (i - 1). If DP[i - 1] is not 0 means we have something like this “(())” . This will have DP “0024"
4, We might have something before "(())”. Take "()(())” example, Check the i = 1 because this might be a consecutive valid string.
public class Solution {
public int longestValidParentheses(String s) {
int[] dp = new int[s.length()];
int result = 0;
int leftCount = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
leftCount++;
} else if (leftCount > 0){
dp[i] = dp[i - 1] + 2;
dp[i] += (i - dp[i]) >= 0 ? dp[i - dp[i]] : 0;
result = Math.max(result, dp[i]);
leftCount--;
}
}
return result;
}
}https://leetcode.com/articles/longest-valid-parentheses/
We make use of a array where th element of represents the length of the longest valid substring ending at th index. We initialize the complete array with 0's. Now, it's obvious that the valid substrings must end with . This further leads to the conclusion that the substrings ending with will always contain '0' at their corresponding indices. Thus, we update the array only when is encountered.
To fill array we will check every two consecutive characters of the string and if
- and , i.e. string looks like
We do so because the ending "()" portion is a valid substring anyhow and leads to an increment of 2 in the length of the just previous valid substring's length. - and , i.e. string looks likeif then
The reason behind this is that if the 2nd last was a part of a valid substring (say ), for the last to be a part of a larger substring, there must be a corresponding starting which lies before the valid substring of which the 2nd last is a part (i.e. before ). Thus, if the character before happens to be , we update the as an addition of in the length of which is . To this, we also add the length of the valid substring just before the term "(,sub_s,)" , i.e. .
http://www.sigmainfy.com/blog/leetcode-longest-valid-parentheses.html
Define f(i) to be the longest length of the valid parentheses ended at s[i], and only the following two cases, dp[i] could be calculated from a recursive definition, otherwise it is zero.
- if s[i] is ‘)’ and s[i-1] is equal to ‘(‘, then dp[i] = dp[i-2] + 2
- if s[i] is ‘)’ and s[i-1] is equal to ‘)’ and s[i - dp[i-1] – 1] is equal to ‘(‘, then dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] – 2]
int longestValidParentheses(string s) {
int n = s.size();
int len = 0;
vector<int> dp(n, 0);
for (int i = 1; i < n; ++i) {
if (')' == s[i]) {
if ('(' == s[i-1]) {
dp[i] = 2;
if (i >= 2)
dp[i] += dp[i-2];
}
else {
int idx = i - dp[i-1] - 1;
if (idx >= 0 && '(' == s[idx]) {
dp[i] = dp[i-1] + 2;
if (idx > 0)
dp[i] += dp[idx -1];
}
}
}
len = max(len, dp[i]);
}
return len;
}
状态转移方程：(为了方便，假设下面的指针都是合法的)
1. 当s[i] = '(' 时，显然不需要处理，dp[i] = 02. 当s[i] = ')' 时，此时s[i - 1] 有两种情况2.1 s[i - 1] = '('。表示s[i]匹配成功，要验证dp[i - 2]的状态，以判断是否可以与前面的相连2.2 s[i - 1] = ')'。表示s[i]并不一定能匹配成功，要验证dp[i - dp[i - 1] - 2] 的状态。
2 public int longestValidParentheses(String s) { 3 if(s == null || s.length() < 2) return 0; 4 int max = 0,length = s.length(); 5 char[] sc = s.toCharArray(); 6 int[] dp = new int[length]; 7 Stack<Character> stack = new Stack<Character>(); 8 for(int i = 1; i < length; i++){ 9 if(sc[i] == '(') continue; 10 if(sc[i - 1] == '('){ 11 dp[i] = 2; 12 if(i - 2 >= 0) dp[i] += dp[i - 2]; 13 }else{ 14 if(dp[i - 1] > 0){ 15 int leap = dp[i - 1]; 16 if(i - 1 - leap >= 0 && sc[i - 1 - leap] == '('){ 17 dp[i] = dp[i - 1] + 2; 18 if(i - leap - 2 >= 0) dp[i] += dp[i - leap - 2]; 19 } 20 } 21 } 22 max = Math.max(max,dp[i]); 23 } 24 return max; 25 }http://dp2.me/blog/?p=482
int longestValidParentheses(string s) {
stack<int> lefts;
int result = 0;
int start = 0;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(') {
lefts.push(i);
} else if (!lefts.empty()){
lefts.pop();
if (lefts.empty()) {
result = max(result, i - start + 1);
} else {
result = max(result, i - lefts.top());
}
} else {
start = i + 1;
}
}
return result;
}
http://www.zrzahid.com/longest-valid-parenthesis/Better solution – O(1) Constant Space Solution
a string becomes invalid for the first unmatched ‘)’ or the last unmatched
We can actually find maximum length valid substring by scanning left to right and keep counting valid pairs (increment length by 2 for each match) until we see a unmatched ‘)’. A valid pair would contribute 0 to overall count but would contribute 2 to length. So, whenever we see count == 0 this will indicate end of a local maxima. So, update global max at that point only. This will compute max substring that ends with unmatched ‘)’. This is not global max because there can be max substring with invalid ‘(‘. For example, ()())(((()). In order to find maximum substring that can have invalid ‘(‘ we can scan from right to left and do the above same counting procedure. Final global maxima would be the maximum of the two global maxima computed from both end.
public static int longestValidParenthesis(String str, int dir){ int start = 0; int end = str.length()-1; int openChar = '('; int count = 0; int maxLen = 0; int curLen = 0; if(dir == -1){ start = end; end = 0; openChar = ')'; } for(int i = start; i!=end; i+=dir){ if(str.charAt(i) == openChar){ count++; } else{ //no matching left if(count <= 0){ //restart curLen = 0; } else{ //a local match count--; curLen += 2; if(count == 0){ maxLen = Math.max(maxLen, curLen); } } } } return maxLen; } public static int longestValidParenthesis2(String str){ return Math.max(longestValidParenthesis(str, 1), longestValidParenthesis(str, -1)); }
O(n) time and O(n) space
1. Scan each character left to right
2. If current character is '(' then this is part of current local maxima. Push the position into a stack to compute length of local of local maxima later when we see a ending parenthesis.
3. If current character is ')' then we have 2 cases -
3a. If stack is empty - this means we don't have any local maxima so we can start a new local maxima from next position by setting a start position of local maxima to the index.
3b. If stack is not empty - this means we already have a local maxima with. So, pop out the matching '('. We have two sub cases -
3b.i. The stack is empty - this means we just finished a local maxima. So, we can compute length of local maxima using the start position we are maintaining, that is len = i-start. Update the global maxima.
3b.ii. The stack is not empty - this means we have more open parenthesis in current local maxima to match. So, we are extending a local maxima here. The start of the local maxima so far would be top of the stack. So, we compute len = i-stack.top() and update global maxima accordingly.
public static int longestValidParenthesis(String str){ int maxLen = 0; int start = -1; Stack<Integer> stack = new Stack<Integer>(); for(int i = 0; i<str.length(); i++){ if(str.charAt(i) == '('){ stack.push(i); } else{ //no matching left if(stack.isEmpty()){ start = i; } else{ stack.pop(); if(!stack.isEmpty()){ maxLen = Math.max(maxLen, i-stack.peek()); } else{ maxLen = Math.max(maxLen, i-start); } } } } return maxLen; }
def isValid(str) :
int count;
foreach(character c in str)
if (c == '(') then
count++;
else
if(count == 0)
return false;
count--;
end
end
return (count == 0)
end
X. https://discuss.leetcode.com/topic/8305/simple-java-solution
public int longestValidParentheses(String s) {
char[] S = s.toCharArray();
int[] V = new int[S.length];
int open = 0;
int max = 0;
for (int i=0; i<S.length; i++) {
if (S[i] == '(') open++;
if (S[i] == ')' && open > 0) {
V[i] = 2 + V[i-1] + (i-2-V[i-1] > 0 ? V[i-2-V[i-1]] : 0);
open--;
}
if (V[i] > max) max = V[i];
}
return max;
}
When right parentheses are more than left parentheses in the forward pass, we can discard previous parentheses. In the backward pass, when left parentheses are more than right parentheses, we can discard previous parentheses.
int longestValidParentheses(string s) {
int longest = 0;
int extra=0;
int length=0;
for(int i=0; i<s.size(); i++) {
if(s[i] == '(') {
extra++;
length++;
}
else {
if(extra>0) {
extra--;
length++;
if(extra == 0)
longest = max(longest, length);
}
else {
extra = 0;
length=0;
}
}
}
length = 0;
extra=0;
for(int i=s.size()-1; i>=0; i--) {
if(s[i] == ')') {
extra++;
length++;
}
else {
if(extra>0){
extra--;
length++;
if(extra == 0)
longest = max(longest, length);
}
else {
extra = 0;
length=0;
}
}
}
return longest;
}X. https://leetcode.com/articles/longest-valid-parentheses/
Time complexity : . Generating every possible substring from a string of length requires . Checking validity of a string of length requires .
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push('(');
} else if (!stack.empty() && stack.peek() == '(') {
stack.pop();
} else {
return false;
}
}
return stack.empty();
}
public int longestValidParentheses(String s) {
int maxlen = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i + 2; j <= s.length(); j += 2) {
if (isValid(s.substring(i, j))) {
maxlen = Math.max(maxlen, j - i);
}
}
}
return maxlen;
}
