Algorithm for Finding Length Of The Longest Valid String

(2614 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:

Solution Worked 1 UpvotesUpvote

        

Solution Didn't Worked 0 DownvotesDownvote



Comments



Search

Play 2048 Game Online

Search Tags

    Find Length of Longest Valid String