Longest Valid Parenthesis

Introduction

A sequence of parentheses is called balanced if, for every opening bracket, there is a unique closing bracket. A substring is a continuous part of a string. In the context of this problem, a valid substring is a balanced substring. 

In this blog, we’ll learn how to find the longest valid parentheses substring and get the most efficient solution. 

Let’s understand the problem statement in-depth to get a better understanding.

Problem Statement

Given a string consisting of characters ‘(‘ and ‘),’ find the length of the longest valid i.e. well-formed parentheses substring.

For example: 

INPUT : s= “(()”

OUTPUT:  2

The longest valid substring will be “()” from index 1 to 2, and its length is 2.

INPUT : s= “)()())”

OUTPUT:  4

The longest valid substring will be “()()” from index 1 to 4, and its length is 4.

INPUT : s= “”

OUTPUT:  0

The string is empty; therefore, no valid substring, and the answer is 0.

Recommended: Please try it on “CodeStudio”, before moving on to the solution approach.

Approach 1: Using Stack

A simple solution would be to find all the substrings and check which of them are balanced and find the one with maximum length. But this solution will have a complexity of O(n^3).

O(n^2) for generating all the substrings and O(n) for checking if it’s balanced or not. The complexity is very high, so we look for better solutions.

There are two ways to solve this problem in O(n) time. Both are quite different in their implementation and ideology. Let’s have a look at both of them one by one. 

The approach is to store the indexes of previous starting indexes in a stack

Steps are : 

  • Initially push -1 to the stack and initialize an answer variable to 0.
  • Start iterating from i=0 to i<s.length() of the string. 
    • If the current character, i.e; s[i] ==’(’, push its index, i.e; i into the stack. 
    • Else if s[i]==’)’, 
      • If the stack is empty, push i into the stack.
      • Otherwise, pop the top item from the stack. Then, 
        • if the stack is not empty, the length of the current substring will be the difference between the current index and the top of the stack. If this current length is greater than our ans, update the ans. 
        • If the stack becomes empty, push the current index into it.
  • Return ans.

Code

#include<iostream>
#include <bits/stdc++.h>
using namespace std;

int maxlen(string s){
    int n = s.length();
    int ans = 0;
    stack<int>st;


    for(int i=0;i<n;i++){
        if(s[i]=='('){
            st.push(i);
        }
        else{
            if(st.empty()==0){
                st.pop();
            }
            if(st.empty()==0){
                ans = max(ans, abs(i-st.top()));
            }
            else{
                st.push(i);
            }
        }
    }


    return ans;
}

int main(){
    string s;
    cin>>s;
    int ans= maxlen(s);
    cout<<ans<<endl;
    return 0;
}

Input

)()())

Output

4

Time complexity

O(n), where n is the length of the input string.

Reason: Because we’re iterating through the whole string once.

Space complexity

O(n), where n is the length of the input string.

Reason: For storing the indexes of characters of the string into the stack.

Approach 2: Using Dynamic Programming 

This problem can also be solved using dynamic programming. We have a dp table of size n where dp[i] would store the length of the longest valid substring ending at s[i]. 

Steps are: 

  • Initialize the dp table of size n with initial values equals 0. Also, declare initialize an answer variable with a value equal to 0.
  • Now iterate through the whole string from i=0 to i<n
    • If s[i]==’(‘, we know that no valid substring can end at an opening bracket, therefore, dp[i] = 0;
    • If s[i]==’)’,
      • If s[i-1]==’(‘, the string is like “.....()”. Therefore, the answer for this would depend on the answer for the index i-2. This index would just add 2 to the answer of the index i-2. Thus, dp[i] = dp[i-2]+2.
      • If s[i-1]==’)‘, the string is like “.....))”, then, this s[i] would make a valid substring only if s at i-dp[i-1]-1 is ‘(‘ because the substring from i-dp[i-1] to i-1 will itself be a valid substring and we can only add on it from both the ends. So, if s[i-dp[i-1]-1]==’(‘ them, dp[i] = dp[i-1]+2+dp[i-dp[i-1]-2].
  • For each I, after we’ve calculated the value of dp[i], if it is greater than our current ans, update ans.
  • Return ans.

Code

#include<iostream>
#include <bits/stdc++.h>
using namespace std;

int maxlen(string s){
    int n = s.length();
    vector<int>dp(n,0);
    int ans = 0;
    for(int i=0;i<n;i++){
        if(s[i]=='('){
            dp[i] = 0;
        }
        else{
            if(s[i-1]=='('){
                dp[i] = dp[i-2]+2;
            }
            else{
                if(i-dp[i-1]-1>=0 && s[i-dp[i-1]-1]=='('){
                    dp[i] = dp[i-1]+2;
                    if(i-dp[i-1]-2>=0){
                        dp[i]+=dp[i-dp[i-1]-2];
                    }
                }
            }
        }
        ans = max(ans,dp[i]);
    }
    return ans;
}

int main(){
    string s;
    cin>>s;
    int ans= maxlen(s);
    cout<<ans<<endl;
    return 0;
}

Input

)()())

Output

4

Time complexity

O(n), where n is the length of the input string.

Reason: Because we’re iterating through the whole string once.

Space complexity

O(n), where n is the length of the input string.

Reason: For storing the dp values for all indexes. 

Approach 3: Using Constant Space 

In the earlier two approaches, the space complexity was O(n). This problem can also be solved in O(1) space. 

Steps are: 

  • Declare and initialize three variables L, R, and ans to 0.
  • Now iterate through the whole string left to right from i=0 to i<n
  • If s[i]==’(‘ increment L by 1.
  • If s[i]==’)’ increment R by 1.
  • Whenever L==R, we’ve found a valid substring as each opening bracket has a corresponding closing bracket. And the length of this substring will be L+R. Update ans variable if this length is greater than ans.
  • If at any incidence, R>L, i.e.; the number of closing brackets is greater than the number of opening brackets, we’re sure that this is an invalid substring. Therefore, set the L and R to 0 and start from the next index.
  • Again, iterate through the whole string from right to left, i.e., from i=n-1 to i==0. 
    • This is done because it is possible to miss the longest substring while we traverse left to right.
    • For example, the string “(()()” will give zero maximum length in the forward pass, as L and R never become equal, whereas the correct answer is 4.
    • To correct these cases, we do a backward traversal.
    • If s[i]==’(‘ increment L by 1.
    • If s[i]==’)’ increment R by 1.
    • Whenever L==R, we’ve found a valid substring as each opening bracket has a corresponding closing bracket. And the length of this substring will be L+R. Update ans variable if this length is greater than ans.
    • If at any incidence, L>R, i.e.; the number of closing brackets is greater than the number of opening brackets, we’re sure that this is an invalid substring. Therefore, set the L and R to 0 and start from the next index.
  • Return ans. 

Code

#include<iostream>
#include <bits/stdc++.h>
using namespace std;

int maxlen(string s){
    int n = s.length();
    int L=0;
    int R=0;
    int ans=0;
    for(int i=0;i<n;i++){
        if (s[i] == '(')
            L++;
        else
            R++;
        if (L==R)
            ans = max(ans, L+R);
        else if (R>L)
            L=R=0;
    }
    L= R = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '(')
            L++;
        else
            R++;
        if (L==R)
            ans = max(ans, L+R);
        else if (L>R)
            L=R=0;
    }
    return ans;
}

int main(){
    string s;
    cin>>s;
    int ans= maxlen(s);
    cout<<ans<<endl;
    return 0;
}

Input

)()())

Output

4

Time complexity

O(n), where n is the length of the input string.

Reason: Because we’re iterating through the whole string twice.

Space complexity

O(1)

Reason: No other space than just making the variables.

Frequently asked questions

  1. What is dynamic programming, and where is it used?
    Dynamic programming is an optimization method used in various programming problems. It is used in problems where the solution depends on smaller overlapping subproblems. We use it to memorize the results so that they can easily be used later when needed.
     
  2. What are overlapping subproblems?
    A problem has overlapping subproblems if it can be divided into smaller problems that are reused multiple times.
     
  3. Where can I submit my “Longest valid parentheses” code?
    You can submit your code on CodeStudio and get it accepted here right away.
     
  4. What is a balanced parentheses string?
    A string of parentheses is intuitively balanced if each left parentheses has a matching right parentheses and the matched pairs are well nested.
     
  5. How do you know if a parentheses string is balanced?
    Using a stack, you can find out if a parentheses string is balanced or not. For detailed information, refer to this.

Key takeaways

In this article, we’ve discussed the longest valid parentheses problem. There are various problems with strings consisting of parentheses such as Valid ParenthesesGenerate all parenthesesDifferent ways to add parentheses, and Remove invalid parentheses

I would suggest you solve them to gain more confidence on this topic. These questions are asked during various coding contests as well as placements tests.

To practice more such problems, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think