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(N³) 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:

1. Reverse a String using Stack
2. Implement two stacks in a single array
3. Print Bracket Number
4. Next Greater Frequency Element
5. Sort a Stack using Temporary Stack
6. Check whether given Parentheses String are Balanced Parentheses or Not.
7. Next Greater Element
8. Find Minimum number of bracket reversals required to make an expression balanced.
9. Implement Queue Using Two Stacks.
10. Merge Overlapping Intervals using Stacks
11. Implement Stack Using Linked List
12. Largest Rectangular Area in Histogram
13. Program to print Alternate Elements of an Array.
14. Program to swap kth element from beginning to kth element from end in an Array.
15. Program to print all possible subarrays of the given array.
16. Program to print kth smallest and kth largest element of an Array.
17. Program to find equilibrium index of an Array.
18. Program to find majority element of an Array.
19. Program to find mean of the Array.
20. Program to sort an Array of 0s and 1s.