Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach 1: Using Stack
3.1.
Code
3.2.
Time complexity
3.3.
Space complexity
4.
Approach 2: Using Dynamic Programming 
4.1.
Code
4.2.
Time complexity
4.3.
Space complexity
5.
Approach 3: Using Constant Space 
5.1.
Code
5.2.
Time complexity
5.3.
Space complexity
6.
Frequently asked questions
6.1.
What are Longest valid parentheses?
6.2.
How do you find the longest valid parentheses?
6.3.
How many balanced parentheses are there?
6.4.
How do you find the longest valid parentheses in Python?
6.5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Longest Valid Parentheses

Author Shreya Deep
1 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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.

longest valid parentheses

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 “Coding Ninjas Studio”, before moving on to the solution approach.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

Also check out - Substr C++

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.

Check out Longest Common Substring

Frequently asked questions

What are Longest valid parentheses?

The longest valid parentheses challenge entails ensuring that all parentheses match, meaning that each opening parenthesis has a corresponding closing parenthesis. An opening parenthesis should appear before a closing parenthesis, which is how the matched parentheses are arranged. The length of that valid pair of parentheses is maximum.

How do you find the longest valid parentheses?

There are many approaches to finding the longest valid parentheses. A simple solution would be to find all the substrings and check which of them are balanced and find the one with the maximum length. Another is dynamic programming, dp[i] would store the length of the longest valid substring. 

How many balanced parentheses are there?

To find the valid/balanced parentheses, the matched pairs are correctly nested, and there must be one right parentheses for every left one. And we have to calculate all the valid parentheses like this. Then count the total number and display the total number of balanced/valid parentheses. 

How do you find the longest valid parentheses in Python?

We will see if we encounter any opening parentheses, and we will insert them in stack, else, pop the top element from the stack if the stack is not empty, the top of the stack does not equal zero, and s[stack top] is opening parenthesis. We will update ans variable.

Conclusion

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

Check out this article - Balanced Parentheses  Fibonacci Series in Python

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, Coding Ninjas Studio 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!

Previous article
Maximal Square
Next article
Minimum Sum Path in a Matrix
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass