# Length of Longest valid Substring

Difficulty Level Hard
StringViews 2354

## Problem Statement

In the “Length of Longest valid Substring” we have given a string that contains the opening and closing parenthesis only. Write a program that will find the longest valid parenthesis substring.

## Input Format

The first and only one line containing a string s.

## Output Format

The first and only one line containing an integer n denoting the length of the longest valid parenthesis substring.

## Constraints

• 1<=|s|<=10^5
• s[i] must be ‘(‘ or ‘)’

## Example

`(())())`
`6`

Explanation:  “(())()” is the longest valid parenthesis substring in above-given string. So our answer is 6.

## Algorithm for Length of Longest valid Substring

1. Create an empty stack and push -1 to it. -1 is to provide base case for next valid string

2. create a variable ‘res’ to store the output

3. Traverse all characters from start to end

a. If the character is ‘(‘, then push current index to the stack
b. Else,

• Pop an element from the stack.
• If the stack is not empty,  then find the length of a current valid substring by taking the difference between the current index and the top of the stack. Check if the current length is more than the result, then update the result.
• If the stack is empty, push the current index as the base for the next valid substring.

4. Return ‘res’

Implementation of the algorithm-

s = “(())”
push -1 into stack, and initialize res = 0

i = 0, s = ‘(‘,  push 0 into stack, now stack = [-1,0]
i = 1, s = ‘(‘,  push 1 into stack, now stack = [-1,0,1]
for i = 2, s = ‘)’, pop() so now stack = [-1,0]
res = max(res, i – stack.top()) = max(0, 2-0) = max(0,2) = 2
i = 3, s = ‘)’, pop() so now stack = [-1]
res = max(res, i – stack.top()) = max(2, 3-(-1)) = max(2,4) = 4

Therefore, longest length is = res = 4.

## Implementation

### C++ Program for Length of Longest valid Substring

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

int maxLength(string s)
{
int n = s.length();

// Create a stack and push -1 as initial index to it.
stack<int> stck;
stck.push(-1);

// Initialize res
int res = 0;

// Traverse all characters of given string
for (int i=0; i<n; i++)
{
// If opening bracket, push index of it
if (s[i] == '(')
stck.push(i);

else // If closing bracket, i.e.,s[i] = ')'
{
// Pop the previous opening bracket's index
stck.pop();

// Check if this length formed with base of
// current valid substring is more than max
// so far
if (!stck.empty())
res = max(res, i - stck.top());

// If stack is empty. push current index as
// base for next valid substring (if any)
else stck.push(i);
}
}

return res;
}

int main()
{
string s;
cin>>s;
cout<<maxLength(s)<<endl;
return 0;
}```

### Java Program for Length of Longest valid Substring

```import static java.lang.Math.max;
import java.util.Scanner;
import java.util.Stack;
class sum
{
public static int maxLength(String s)
{
int n = s.length();

// Create a stack and push -1 as initial index to it.
Stack<Integer> stck = new Stack<Integer>();
stck.push(-1);
// Initialize res
int res = 0;
// Traverse all characters of given string
for (int i=0; i<n; i++)
{
// If opening bracket, push index of it
if(s.charAt(i) == '(')
stck.push(i);

else // If closing bracket, i.e.,s[i] = ')'
{
// Pop the previous opening bracket's index
stck.pop();

// Check if this length formed with base of
// current valid substring is more than max
// so far
if(stck.size()>0)
res = max(res, i - (Integer) stck.peek());
// If stack is empty. push current index as
// base for next valid substring (if any)
else stck.push(i);
}
}
return res;
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
String s = sr.next();
System.out.println(maxLength(s));
}
}```
`(()())((`
`6`

## Complexity Analysis for Length of Longest valid Substring

### Time Complexity

O(n) where n is the size of the given string. Here we traverse while string char by char and perform some operations in constant time.

### Space Complexity

O(n) because we use the stack. Here the maximum size of the stack will be n.

Translate »