Do you think IIT Guwahati certified course can help you in your career?
No
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 “Coding Ninjas Studio”, 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.
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.
intmaxlen(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; }
intmain(){ string s; cin>>s; int ans= maxlen(s); cout<<ans<<endl; return0; }
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.
intmaxlen(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); elseif (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); elseif (L>R) L=R=0; } return ans; }
intmain(){ string s; cin>>s; int ans= maxlen(s); cout<<ans<<endl; return0; }
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.
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.
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!
Live masterclass
Become a YouTube Analyst: Use Python to analyze viewers data
by Coding Ninjas
04 Feb, 2025
02:30 PM
Get hired as an Amazon SDE : Resume building tips
by Coding Ninjas
03 Feb, 2025
02:30 PM
Expert tips: Ace Leadership roles in Fortune 500 companies
by Coding Ninjas
03 Feb, 2025
12:30 PM
Become a YouTube Analyst: Use Python to analyze viewers data