Home » Technical Interview Questions » String Interview Questions » Length of longest valid substring

# Length of longest valid substring

## Given a string which contains opnening and closing paranthesis, write a function that will find the longest valid parenthesis substring

### Example

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

OUTPUT
6
“(())()” is the longest valid paranthesis substring in above example

Time Complexity : O(n)

## Algorithm

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,
i) Pop an element from the stack
ii) If stack is not empty,  then find length of current valid  substring by taking difference between current index and top of the stack. If current length is more than result, then update the result.
iii) If stack is empty, push current index as base for 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]
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.

## C++ Program

```#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 = "()(())";
cout << maxLength(s) << endl ;

return 0;
}```

READ  Longest Common Prefix using Sorting

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions