# Length of Longest Valid Substring

Length of Longest Valid Substring” is one of the famous technical and algorithmic interview problem based on stack data structure. Here, we are given a string consisting of open and closing parentheses and our task is to find the length of longest valid substring.

Example:

String: ((()()
Length of Longest Valid Substring: 4
String: (()())(()
Length of Longest Valid Substring: 6
String: ((((
Length of Longest Valid Substring: 0

To find the length of Longest Valid Substring, two methods can be used:

1. Brute-Force Method
2. Stack Based Method

METHOD 1: Brute-Force Method

The steps required to find the length of longest valid substring are as follows:

1. Generate All the Possible Substrings of the given string.
2. Now, out of all generated substring, find the substrings which are balanced.
3. Out of all balanced substring, find the substring with longest length.

The following solution seems very simple, but it very time costly and is inefficient. To find all the possible substring, the time complexity will be O(N3) and then to check whether substring is valid or not will take O(n).

So, this solution is very time costly.

METHOD 2: Stack Based Method

The steps required to find the length of longest valid substring are as follows:

1. Create an empty stack and push ‘-1’ into the stack. Here, ‘-1’ will provide the base case for next valid substring.
2. Initialize a variable, ‘max_len’ with zero, which will store the result.
3. Start iterating the string, character by character:
4. If the character is an opening parentheses, ‘(‘, then push the index of current character into the stack.
5. If the character is a closing parentheses, ‘)’, pop the top element of the stack and then we have two choices:
1. If the stack is empty, then push the index of current character into the   stack, which will work as base for next valid substring.
2. If the stack is not empty, then find the length of longest valid substring by taking difference between index of current element and top element of stack.

Then, check if the current length is greater than ‘max_length’, if current length is greater than current length, then assign ‘max_length’ with current length.

6. Return and print the result.

The time complexity of this solution is O(n).

#### C++ Program to print the length of longest valid substring is as follows:

/* C++ Program to find and print longest valid substring */
#include<bits/stdc++.h>
using namespace std;

/* Function to find longest valid substring */
int longestValidSubstring(string str)
{
/*
Create an empty stack and push '-1' to the stack.
'-1' will work as base case for next valid substring
*/
stack<int> st;
st.push(-1);

int max_len = 0;

/* Traverse the complete String */
for(int i = 0; i < str.length(); i++)
{
/*
If the current character is opening parentheses, '(',
then push current index into the stack.
*/
if(str[i] == '(')
{
st.push(i);
}
else if(str[i] == ')')
{
/* Pop the top element of the stack */
st.pop();

/*
If the current character is closing parentheses, ')',
then there are two options:
1. If the stack is empty, then push the current index, which
will work as base for next valid substring.
2. IF the stack is not empty, then find the length of longest
valid substring by taking difference between index of current
element and top element of stack.
*/
if(st.empty())
{
st.push(i);
}
else
{
max_len = max(max_len,i - st.top());
}
}
}
return max_len;
}

int main()
{
string str = "(())()(()";
int res = longestValidSubstring(str);
cout<<"The length of longest valid substring is "<<res;
}
OUTPUT:
The length of longest valid substring is 6

Related Posts: