Given a string consisting of opening and closing parenthesis, find the length of the longest valid parenthesis substring.
Examples:
Input : ((()
Output : 2
Explanation : ()
Input: )()())
Output : 4
Explanation: ()()
Input: ()(()))))
Output: 6
Explanation: ()(())
A Simple Approach is to find all the substrings of given string. For every string, check if it is a valid string or not. If valid and length is more than maximum length so far, then update maximum length. We can check whether a substring is valid or not in linear time using a stack (See this for details).
Time complexity of this solution is O(n3).
Space Complexity: O(1)
An Efficient Solution can solve this problem in O(n) time. The idea is to store indexes of previous starting brackets in a stack. The first element of the stack is a special element that provides index before the beginning of valid substring (base for next valid string).
1) Create an empty stack and push -1 to it.
The first element of the stack is used
to provide a base for the next valid string.
2) Initialize result as 0.
3) If the character is '(' i.e. str[i] == '('),
push index'i' to the stack.
2) Else (if the character is ')')
a) Pop an item from the stack (Most of the
time an opening bracket)
b) If the stack is not empty, then find the
length of current valid substring by taking
the difference between the current index and
top of the stack. If current length is more
than the result, then update the result.
c) If the stack is empty, push the current index
as a base for the next valid substring.
3) Return result.
Below is the implementation of the above algorithm.
C++
#include <bits/stdc++.h>
using namespace std;
int findMaxLen(string str)
{
int n = str.length();
stack< int > stk;
stk.push(-1);
int result = 0;
for ( int i = 0; i < n; i++)
{
if (str[i] == '(' )
stk.push(i);
else
{
if (!stk.empty())
{
stk.pop();
}
if (!stk.empty())
result = max(result, i - stk.top());
else
stk.push(i);
}
}
return result;
}
int main()
{
string str = "((()()" ;
cout << findMaxLen(str) << endl;
str = "()(()))))" ;
cout << findMaxLen(str) << endl;
return 0;
}
|
Java
import java.util.Stack;
class Test
{
static int findMaxLen(String str)
{
int n = str.length();
Stack<Integer> stk = new Stack<>();
stk.push(- 1 );
int result = 0 ;
for ( int i = 0 ; i < n; i++)
{
if (str.charAt(i) == '(' )
stk.push(i);
else
{
if (!stk.empty())
stk.pop();
if (!stk.empty())
result
= Math.max(result,
i - stk.peek());
else
stk.push(i);
}
}
return result;
}
public static void main(String[] args)
{
String str = "((()()" ;
System.out.println(findMaxLen(str));
str = "()(()))))" ;
System.out.println(findMaxLen(str));
}
}
|
Python3
def findMaxLen(string):
n = len (string)
stk = []
stk.append( - 1 )
result = 0
for i in range (n):
if string[i] = = '(' :
stk.append(i)
else :
if len (stk) ! = 0 :
stk.pop()
if len (stk) ! = 0 :
result = max (result,
i - stk[ len (stk) - 1 ])
else :
stk.append(i)
return result
string = "((()()"
print (findMaxLen(string))
string = "()(()))))"
print (findMaxLen(string))
|
C#
using System;
using System.Collections.Generic;
class GFG {
public static int findMaxLen( string str)
{
int n = str.Length;
Stack< int > stk = new Stack< int >();
stk.Push(-1);
int result = 0;
for ( int i = 0; i < n; i++)
{
if (str[i] == '(' ) {
stk.Push(i);
}
else
{
if (stk.Count > 0)
stk.Pop();
if (stk.Count > 0)
{
result
= Math.Max(result,
i - stk.Peek());
}
else {
stk.Push(i);
}
}
}
return result;
}
public static void Main( string [] args)
{
string str = "((()()" ;
Console.WriteLine(findMaxLen(str));
str = "()(()))))" ;
Console.WriteLine(findMaxLen(str));
}
}
|
Javascript
<script>
function findMaxLen(str)
{
let n = str.length;
let stk = [];
stk.push(-1);
let result = 0;
for (let i = 0; i < n; i++)
{
if (str.charAt(i) == '(' )
{
stk.push(i);
}
else
{
if (stk.length != 0) {
stk.pop();
}
if (stk.length != 0) {
result = Math.max(result, i - stk[stk.length - 1]);
}
else {
stk.push(i);
}
}
}
return result;
}
let str = "((()()" ;
document.write(findMaxLen(str) + "<br>" );
str = "()(()))))" ;
document.write(findMaxLen(str) + "<br>" );
</script>
|
Time Complexity: O(N), here N is the length of string.
Auxiliary Space: O(N)
Explanation with example:
Input: str = "(()()"
Initialize result as 0 and stack with one item -1.
For i = 0, str[0] = '(', we push 0 in stack
For i = 1, str[1] = '(', we push 1 in stack
For i = 2, str[2] = ')', currently stack has
[-1, 0, 1], we pop from the stack and the stack
now is [-1, 0] and length of current valid substring
becomes 2 (we get this 2 by subtracting stack top from
current index).
Since the current length is more than the current result,
we update the result.
For i = 3, str[3] = '(', we push again, stack is [-1, 0, 3].
For i = 4, str[4] = ')', we pop from the stack, stack
becomes [-1, 0] and length of current valid substring
becomes 4 (we get this 4 by subtracting stack top from
current index).
Since current length is more than current result,
we update result.
Another Efficient Approach can solve the problem in O(n) time. The idea is to maintain an array that stores the length of the longest valid substring ending at that index. We iterate through the array and return the maximum value.
1) Create an array longest of length n (size of the input
string) initialized to zero.
The array will store the length of the longest valid
substring ending at that index.
2) Initialize result as 0.
3) Iterate through the string from second character
a) If the character is '(' set longest[i]=0 as no
valid sub-string will end with '('.
b) Else
i) if s[i-1] = '('
set longest[i] = longest[i-2] + 2
ii) else
set longest[i] = longest[i-1] + 2 +
longest[i-longest[i-1]-2]
4) In each iteration update result as the maximum of
result and longest[i]
5) Return result.
Below is the implementations of the above algorithm.
C++
#include <bits/stdc++.h>
using namespace std;
int findMaxLen(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;
}
int main()
{
string str = "((()()" ;
cout << findMaxLen(str) << endl;
str = "()(()))))" ;
cout << findMaxLen(str) << endl;
return 0;
}
|
Java
import java.util.*;
class GFG
{
static int findMaxLen(String s)
{
if (s.length() <= 1 )
return 0 ;
int curMax = 0 ;
int [] longest = new int [s.length()];
for ( int i = 1 ; i < s.length(); i++)
{
if (s.charAt(i) == ')' && i - longest[i - 1 ] - 1 >= 0
&& s.charAt(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 = Math.max(longest[i], curMax);
}
}
return curMax;
}
public static void main(String[] args)
{
String str = "((()()" ;
System.out.print(findMaxLen(str) + "\n" );
str = "()(()))))" ;
System.out.print(findMaxLen(str) + "\n" );
}
}
|
Python3
def findMaxLen(s):
if ( len (s) < = 1 ):
return 0
curMax = 0
longest = [ 0 ] * ( len (s))
for i in range ( 1 , len (s)):
if ((s[i] = = ')'
and i - longest[i - 1 ] - 1 > = 0
and s[i - longest[i - 1 ] - 1 ] = = '(' )):
longest[i] = longest[i - 1 ] + 2
if (i - longest[i - 1 ] - 2 > = 0 ):
longest[i] + = (longest[i -
longest[i - 1 ] - 2 ])
else :
longest[i] + = 0
curMax = max (longest[i], curMax)
return curMax
if __name__ = = '__main__' :
Str = "((()()"
print (findMaxLen( Str ))
Str = "()(()))))"
print (findMaxLen( Str ))
|
C#
using System;
public class GFG {
static int findMaxLen(String s) {
if (s.Length <= 1)
return 0;
int curMax = 0;
int [] longest = new int [s.Length];
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 = Math.Max(longest[i], curMax);
}
}
return curMax;
}
public static void Main(String[] args) {
String str = "((()()" ;
Console.Write(findMaxLen(str) + "\n" );
str = "()(()))))" ;
Console.Write(findMaxLen(str) + "\n" );
}
}
|
Javascript
<script>
function findMaxLen( s) {
if (s.length <= 1)
return 0;
var curMax = 0;
var longest = Array(s.length).fill(0);
for ( var 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 = Math.max(longest[i], curMax);
}
}
return curMax;
}
var str = "((()()" ;
document.write(findMaxLen(str) + "<br\>" );
str = "()(()))))" ;
document.write(findMaxLen(str) + "<br\>" );
</script>
|
Time Complexity: O(N), here N is the length of string.
Auxiliary Space: O(N)
Thanks to Gaurav Ahirwar and Ekta Goel for suggesting above approach.
Another approach in O(1) auxiliary space and O(N) Time complexity:
- The idea to solve this problem is to traverse the string on and keep track of the count of open parentheses and close parentheses with the help of two counters left and right respectively.
- First, the string is traversed from the left towards the right and for every “(” encountered, the left counter is incremented by 1 and for every “)” the right counter is incremented by 1.
- Whenever the left becomes equal to right, the length of the current valid string is calculated and if it greater than the current longest substring, then value of required longest substring is updated with current string length.
- If the right counter becomes greater than the left counter, then the set of parentheses has become invalid and hence the left and right counters are set to 0.
- After the above process, the string is similarly traversed from right to left and similar procedure is applied.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int solve(string s, int n)
{
int left = 0, right = 0, maxlength = 0;
for ( int i = 0; i < n; i++)
{
if (s[i] == '(' )
left++;
else
right++;
if (left == right)
maxlength = max(maxlength, 2 * right);
else if (right > left)
left = right = 0;
}
left = right = 0;
for ( int i = n - 1; i >= 0; i--) {
if (s[i] == '(' )
left++;
else
right++;
if (left == right)
maxlength = max(maxlength, 2 * left);
else if (left > right)
left = right = 0;
}
return maxlength;
}
int solve2(string s, int n){
int left=0,right=0,maxlength=0,t=2;
while (t--){
left=0;
right=0;
for ( int i=0;i<n;i++){
if (s[i]== '(' )left++;
else right++;
if (left==right){
maxlength=max(maxlength,2*left);
}
if (t%2==1 && right>left){
left=0;
right=0;
}
if (t%2==0 && left>right){
left=0;
right=0;
}
}
reverse(s.begin(),s.end());
}
return maxlength;
}
int main()
{
cout << solve( "((()()()()(((())" , 16);
return 0;
}
|
Java
import java.util.Scanner;
import java.util.Arrays;
class GFG {
public static int solve(String s, int n)
{
int left = 0 , right = 0 ;
int maxlength = 0 ;
for ( int i = 0 ; i < n; i++) {
if (s.charAt(i) == '(' )
left++;
else
right++;
if (left == right)
maxlength = Math.max(maxlength,
2 * right);
else if (right > left)
left = right = 0 ;
}
left = right = 0 ;
for ( int i = n - 1 ; i >= 0 ; i--) {
if (s.charAt(i) == '(' )
left++;
else
right++;
if (left == right)
maxlength = Math.max(maxlength,
2 * left);
else if (left > right)
left = right = 0 ;
}
return maxlength;
}
public static void main(String args[])
{
System.out.print(solve( "((()()()()(((())" , 16 ));
}
}
|
Python3
def solve(s, n):
left = 0
right = 0
maxlength = 0
for i in range (n):
if (s[i] = = '(' ):
left + = 1
else :
right + = 1
if (left = = right):
maxlength = max (maxlength, 2 * right)
elif (right > left):
left = right = 0
left = right = 0
for i in range (n - 1 , - 1 , - 1 ):
if (s[i] = = '(' ):
left + = 1
else :
right + = 1
if (left = = right):
maxlength = max (maxlength, 2 * left)
elif (left > right):
left = right = 0
return maxlength
print (solve( "((()()()()(((())" , 16 ))
|
C#
using System;
public class GFG {
public static int solve(String s, int n)
{
int left = 0, right = 0;
int maxlength = 0;
for ( int i = 0; i < n; i++) {
if (s[i] == '(' )
left++;
else
right++;
if (left == right)
maxlength = Math.Max(maxlength,
2 * right);
else if (right > left)
left = right = 0;
}
left = right = 0;
for ( int i = n - 1; i >= 0; i--) {
if (s[i] == '(' )
left++;
else
right++;
if (left == right)
maxlength = Math.Max(maxlength,
2 * left);
else if (left > right)
left = right = 0;
}
return maxlength;
}
public static void Main(String []args)
{
Console.Write(solve( "((()()()()(((())" , 16));
}
}
|
Javascript
<script>
function solve(s, n)
{
let left = 0, right = 0, maxlength = 0;
for (let i = 0; i < n; i++)
{
if (s[i] == '(' )
left++;
else
right++;
if (left == right)
maxlength = max(maxlength, 2 * right);
else if (right > left)
left = right = 0;
}
left = right = 0;
for (let i = n - 1; i >= 0; i--) {
if (s[i] == '(' )
left++;
else
right++;
if (left == right)
maxlength = Math.max(maxlength, 2 * left);
else if (left > right)
left = right = 0;
}
return maxlength;
}
document.write( solve( "((()()()()(((())" , 16));
</script>
|
Time Complexity: O(N), here N is the length of string.
Auxiliary Space: O(1)
Another Approach (Using Memoization):
Intuition:
The problem statement is asking for the length of the longest valid parentheses substring. One way to think about this problem is that for every ‘(‘ we encounter, we need a corresponding ‘)’ somewhere else in the string to form a valid parentheses pair. Therefore, a valid substring must start with an ‘(‘ and end with a ‘)’, and any number of valid parentheses pairs can be in between.
Approach:
The approach used here is to use a stack to keep track of the indexes of the characters in the input string. When a ‘(‘ character is encountered, its index is pushed onto the stack. When a ‘)’ character is encountered, the top index on the stack is popped. The difference between the current index and the top index on the stack represents the length of a valid substring ending at the current index. If the stack is empty after a ‘)’ is popped, it means that no matching ‘(‘ has been found, so the current index is pushed onto the stack as the new base for future valid substrings. By doing so, the solution keeps track of the potential valid parentheses starts and ends, and makes use of the property that any valid parentheses substring must be closed by an earlier opened one. Finally, the algorithm returns the max length at the end of the loop.
Idea : try to break in smaller sub problem .
case 1: string ends at “()”
longestParenEnding(0, i) = longestParenEnding(0, i – 2) + 2
case 2: string ends with “))” for example “()(())”
longestParenEnding(0, i) =
case 3: string ends with “(“
longestParenEnding(0, i) = 0
C++
#include <bits/stdc++.h>
using namespace std;
int lonParen( int i, string& s, vector< int >& memo)
{
if (i <= 0) {
return 0;
}
if (memo[i] != -1) {
return memo[i];
}
if (s[i] == '(' ) {
memo[i] = 0;
}
else if (s[i] == ')' && s[i - 1] == '(' ) {
memo[i] = lonParen(i - 2, s, memo) + 2;
}
else if (s[i] == ')' && s[i - 1] == ')' ) {
int len = lonParen(i - 1, s, memo);
if (i - 1 - len >= 0 && s[i - 1 - len] == '(' ) {
memo[i]
= len + 2 + lonParen(i - len - 2, s, memo);
}
else {
memo[i] = 0;
}
}
return memo[i];
}
int longestValidParentheses(string s)
{
int n = s.size(), maxLen = 0;
vector< int > memo(n, -1);
for ( int i = 0; i < n; i++) {
maxLen = max(maxLen, lonParen(i, s, memo));
}
return maxLen;
}
int main()
{
cout << longestValidParentheses( "((()()()()(((())" );
return 0;
}
|
Java
import java.util.Arrays;
public class Main {
public static int longestValidParentheses(String s) {
int n = s.length();
int maxLen = 0 ;
int [] memo = new int [n];
Arrays.fill(memo, - 1 );
for ( int i = 0 ; i < n; i++) {
maxLen = Math.max(maxLen, lonParen(i, s, memo));
}
return maxLen;
}
public static int lonParen( int i, String s, int [] memo) {
if (i <= 0 ) {
return 0 ;
}
if (memo[i] != - 1 ) {
return memo[i];
}
if (s.charAt(i) == '(' ) {
memo[i] = 0 ;
} else if (s.charAt(i) == ')' && s.charAt(i - 1 ) == '(' ) {
memo[i] = lonParen(i - 2 , s, memo) + 2 ;
} else if (s.charAt(i) == ')' && s.charAt(i - 1 ) == ')' ) {
int len = lonParen(i - 1 , s, memo);
if (i - 1 - len >= 0 && s.charAt(i - 1 - len) == '(' ) {
memo[i] = len + 2 + lonParen(i - len - 2 , s, memo);
} else {
memo[i] = 0 ;
}
}
return memo[i];
}
public static void main(String[] args) {
System.out.println(longestValidParentheses( "((()()()()(((())" ));
}
}
|
Time complexity: O(n),Here, The algorithm has a time complexity of O(n) because it simply iterates the string once.
Auxiliary Space: O(n),Space complexity is O(n) because it uses a stack to keep track of the indexes of the characters in the input string.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!