My DP, O(n) solution without using stack


  • 174
    J

    My solution uses DP. The main idea is as follows: 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.

       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;
            }
    

    Updated: thanks to Philip0116, I have a more concise solution(though this is not as readable as the above one, but concise):

    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] == ')' && 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);
                }
            }
            return curMax;
        }

  • 0
    S

    It seems the formular longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2] is not correct. Consider input "())())", at i = 5, longest array is [0,2,0,0,2,0], longest[5] = longest[4] + 2 + longest[1] = 6. But actually longest[5] is 0.


  • 0
    J

    Please see the condition in the code: if ( i-longest[i-1]-1 >= 0 && s[i-longest[i-1]-1] == '(' ), i-longest[i-1]-1 = 5 - longest[4] -1 = 5 -2 -1 = 2, and s[2] = ')', which is not equal to '('. So the formula will not be executed. longest[5] will remain as 0.


  • 2
    R

    My java solution with both stack and an array....It is very easy to understand. Maybe it is the only good part compared to the other space-saving solution.

    public class Solution {
    	public int longestValidParentheses(String s){
    		if (s==null||s.length()==0) return 0;
    		
    		Stack<Integer> stack= new Stack<Integer>();	//Store indices of '('
    		int[] result=new int[s.length()];//Store the length of the current longest valid sequence.
    		Arrays.fill(result, 0);
    		
    		int max=0;
    		
    		for (int i=0;i<s.length();i++)
    			if (s.charAt(i)=='(')
    				stack.push(i);	
    									
    			else if (s.charAt(i)==')'){
    				if (stack.isEmpty()) 
    					continue;
    				else if (stack.peek()>0) 
    					result[i]=2+result[stack.pop()-1]+result[i-1];//May connect two valid sequences, or increase the length of current valid sequence. 
    				else {
    					result[i]=2+result[i-1];//Handle the special case that the leftmost char is a '('
    					stack.pop();
    				}
    				
    				max=Math.max(result[i],max);
    			}
    		return max;
    	}
    }

  • 7
    P

    I like your solution! And I think it is no need to consider the condition "s[i-1] == '('" since "s[i-longest[i-1]-1] == '('" actually concludes this case. We could just use "if (i-1>=0 && i-longest[i-1]-1 >=0 && s[i-longest[i-1]-1] == '(')"


  • 0
    S

    philip you are right


  • 0
    J

    Yes. You are right, Philip, thank you. Didn't notice that. The solution is based on my thought, never realize that I could optimize it.


  • 0
    C

    I had the same idea, except a bit different handling the current being ) and previous also being ) case. My Python code below:

    def longestValidParentheses(self, s):
        dp = [0]
        left = right = 0
        last = None
        for paren in s:
            if paren == '(':
                left += 1
                dp.append(0)
            else:
                right += 1
                if right > left:
                    dp.append(0)
                    right = left = 0
                    continue
                
                if last == '(':
                    dp.append(dp[-2] + 1)
                else:
                    n = dp[-1] + 1
                    # look back, for cases like ()(())
                    n += dp[-2 * n]
                    dp.append(n)
            last = paren
            
        return 2 * max(dp)

  • 0

    Nice solutions! Very easy to understand. Philip0116's simplification is great!


  • 1
    Z
    class Solution {
    public:
    	int longestValidParentheses(string s) {
    		s = ")" + s;
    		int n = s.length();
    		vector<int> longest(n,0);
    		int res = 0;
    		for (int i=1; i < n; i++) {
    			if (s[i]=='(')
    				longest[i] = 0;
    			else {
    				if (s[i-1]=='(') {
    					longest[i] = longest[i-2] + 2;
    					res = max(res, longest[i]);
    				} else {
    					if (s[i-longest[i-1]-1]=='(') {
    						longest[i] = longest[i-longest[i-1]-2] + longest[i-1] + 2;
    						res = max(res, longest[i]);
    					} 
    				}
    			}
    
    		}
    
    		return res;
    	}
    };
    

    i add a dummy ")". let the code easy to read.


  • 0
    J

    nice solution!!


  • 0
    S

    I tried to use the similar strategy but I got stuck where the 3rd else statement ....


  • 7
    T

    Thanks for your share. The following is edited from your solution. Just add a prefix.

    int longestValidParentheses(string s) {
            s = ")" + s;
            int curMax = 0;
            vector<int> longest(s.size(),0);
            for(int i=1; i < s.length(); i++){
                if(s[i] == ')' && s[i-longest[i-1]-1] == '('){
                        longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2];
                        curMax = max(longest[i],curMax);
                }
            }
            return curMax;
        }
    

    python version:

        def longestValidParentheses(self, s):
            dp, s = [0], ')'+s 
            for i in xrange(1, len(s), 1):
                if s[i] == ')' and s[i - dp[-1] - 1] == '(':
                    dp.append(dp[-1] + 2 + dp[-2-dp[-1]])
                else:
                    dp.append(0)
            return max(dp)

  • 0
    P
    class Solution
    {
    public:
    	int longestValidParentheses(string s) 
    	{
    		int len = s.size(), maxLen = 0, validLeft = 0;
    		vector<int> iCount(len, 0);
    		for (int i = 0; i < len; ++i)
    		{
    			if ('(' == s[i]) ++validLeft;
    			else if (validLeft > 0) 
    			{
    				--validLeft;
    				if ('(' == s[i - 1]) iCount[i] = iCount[i - 2] + 2;
    				else iCount[i] = iCount[i - 1] + 2 + iCount[i - 2 - iCount[i - 1]];
    			}
    			maxLen = iCount[i] > maxLen ? iCount[i] : maxLen;
    		}
    		return maxLen;
    	}
    };

  • 1
    S

    JAVA version. Store the result to the last element of array. Make it one line shorter

    public int longestValidParentheses(String s) {
        s = ")" + s;
        int[] longest = new int[s.length() + 1];
        
        for (int i = 1; i < s.length(); i++){
            if (s.charAt(i) == ')' && s.charAt(i - longest[i - 1] - 1) == '(') {
                longest[i] = longest[i - 1] + 2 + longest[i - longest[i - 1] - 2];
                longest[s.length()] = Math.max(longest[i], longest[s.length()]); 
            }
        }
        
        return longest[s.length()];
    }

  • 0
    B

    Nice, personally, I believe the most natural solution for this problem is via DP.


  • 0
    D

    Here I have question that why longest[i] can be 0 when longest[j] > 0 where 0 < j < i? For example, for input '()((' , when i = 2, the string is '()(' which has a valid subset '()', making the longest[2] = 2, but why longest[2] = 0?


  • 0
    J

    My definition of longest[] array is "for any longest[i], it stores the longest length of valid parentheses which ENDs at i. " So when i = 2, and s[2] =='(', the longest VALID parentheses that ENDS at 2 is of length 0.


  • 0

    what an excellent solution~!!


  • 2
    D

    Great solution, however, i got TLE when trying this.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.