Algorithm for Finding Length Of The Longest Valid String

[2022 views]


If we are given a string consisting of opening and closing parenthesis, let us find the length of longest valid parenthesis-substring.

Examples:

Input : ((()
Output : 2
Explanation : ()

Input: )()())
Output : 4
Explanation: ()() 

Input:  ()(()))))
Output: 6
Explanation:  ()(())

The Solution:

A Simple way is to find all substrings of the given string. For every given string, check if it is a valid string or if it is not. If the string is valid and length is more than the maximum length so far, then we update maximum length. We can check whether the substring is valid or not valid in linear time using the stack. The time complexity of this solution is O(n2).

An Easy & Efficient Solution can solve this problem in O(n) time. The idea is to store indexes of the previous starting brackets in the stack. The first element of the stack is a special element that provides index before the beginning of a valid substring (base for next valid string).

  1. Create an empty stack & push -1 to it. The first element of the stack is used to provide the base for next valid string.
  2. Initialize result as 0.
  3. If the character is '(' i.e. str[i] == '('), push index 'i' to the stack.
  4. Else (if the character is ')')
  5. Pop an item from the stack (Most of the time an opening bracket)
  6. If the stack is not empty, then find the length of a current valid substring by taking the difference b/w the current index & top of the stack. If current length is more than the result, then update the result.
  7. If the stack is empty, push current index as the base for next valid substring.
  8. Return result.
  9. Below is the implementation of the above algorithm in C++
    The Preprocessors:
    #include < bits/stdc++.h > using namespace std;
    The Length Finding Function:
    int findMaxLen(string str) { int n = str.length(); // Create stack & push -1 as initial index to it. stack< int > stk; stk.push(-1); // Initialize result int result = 0; // Traverse all characters of given string for (int i=0; i < n; i++) { // If opening bracket, push index of it if (str[i] == '(') stk.push(i); else // If closing bracket, i.e.,str[i] = ')' { // Pop the previous opening bracket's index stk.pop(); // Check if this length formed with // base of current valid substring is // more than max so far if (!stk.empty()) result = max(result, i - stk.top()); // If stack is empty. push current index as // base for next valid substring (if any) else stk.push(i); } } return result; }

    Main Function:
    int main() { string str = "((()()"; cout << findMaxLen(str) << endl; str = "()(()))))"; cout << findMaxLen(str) << endl ; return 0; }
    Output:
        

Algorithm Logic Test

Our Quiz prepared by Experts Helps you identify your knowledge in Algorithms. Everyone should atleast attempt this Quiz Once. 



Need any help in Programming? Chat with Us

Comments



Online Compiler
Search
Algorithm Quiz

Only 5% Users were able to score above 75% in this Quiz. Can You Crack this?

Deals Ends in





Online Games
Play 2048 Game Online and Relax.
Play 2048 Game Online

Search Tags

    Find Length of Longest Valid String