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:

  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. Infix to Postfix Conversion
  7. Infix to Prefix Conversion
  8. Prefix to Infix Conversion
  9. Prefix to Postfix Conversion
  10. Postfix to Infix Conversion
  11. Postfix to Prefix Conversion
  12. Check whether given Parentheses String are Balanced Parentheses or Not.
  13. Next Greater Element
  14. Find Minimum number of bracket reversals required to make an expression balanced.
  15. Implement Queue Using Two Stacks.
  16. Merge Overlapping Intervals using Stacks
  17. Implement Stack Using Linked List
  18. Largest Rectangular Area in Histogram
  19. Program to find longest palindromic Substring.
  20. Program to check Anagram Strings.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *