Length of Longest valid Substring Length of Longest valid Substring

Table of Contents

Problem Statement

In the “Length of Longest valid Substring” we have given a string that contains the opening and closing parenthesis only. Write a program that will find the longest valid parenthesis substring.

Input Format

The first and only one line containing a string s.

Output Format

The first and only one line containing an integer n denoting the length of the longest valid parenthesis substring.

Constraints

1<=|s|<=10^5
s[i] must be ‘(‘ or ‘)’

Example

(())())

Explanation: “(())()” is the longest valid parenthesis substring in above-given string. So our answer is 6.

Algorithm for Length of Longest valid Substring

1. Create an empty stack and push -1 to it. -1 is to provide base case for next valid string

2. create a variable ‘res’ to store the output

3. Traverse all characters from start to end

a. If the character is ‘(‘, then push current index to the stack
b. Else,

Pop an element from the stack.
If the stack is not empty, then find the length of a current valid substring by taking the difference between the current index and the top of the stack. Check if the current length is more than the result, then update the result.
If the stack is empty, push the current index as the base for the next valid substring.

4. Return ‘res’

Implementation of the algorithm-

s = “(())”
push -1 into stack, and initialize res = 0

i = 0, s[0] = ‘(‘, push 0 into stack, now stack = [-1,0]
i = 1, s[1] = ‘(‘, push 1 into stack, now stack = [-1,0,1]
for i = 2, s[2] = ‘)’, pop() so now stack = [-1,0]
res = max(res, i – stack.top()) = max(0, 2-0) = max(0,2) = 2
i = 3, s[3] = ‘)’, pop() so now stack = [-1]
res = max(res, i – stack.top()) = max(2, 3-(-1)) = max(2,4) = 4

Therefore, longest length is = res = 4.

Implementation

C++ Program for Length of Longest valid Substring

#include<bits/stdc++.h>
using namespace std;
 
int maxLength(string s)
{
    int n = s.length();
 
    // Create a stack and push -1 as initial index to it.
    stack<int> stck;
    stck.push(-1);
 
    // Initialize res
    int res = 0;
 
    // Traverse all characters of given string
    for (int i=0; i<n; i++)
    {
        // If opening bracket, push index of it
        if (s[i] == '(')
          stck.push(i);
 
        else // If closing bracket, i.e.,s[i] = ')'
        {
            // Pop the previous opening bracket's index
            stck.pop();
 
            // Check if this length formed with base of
            // current valid substring is more than max 
            // so far
            if (!stck.empty())
                res = max(res, i - stck.top());
 
            // If stack is empty. push current index as 
            // base for next valid substring (if any)
            else stck.push(i);
        }
    }
 
    return res;
}
 
int main()
{
    string s;
    cin>>s;
    cout<<maxLength(s)<<endl;
    return 0;
}

Java Program for Length of Longest valid Substring

import static java.lang.Math.max;
import java.util.Scanner;
import java.util.Stack;
class sum
{
    public static int maxLength(String s)
    {
        int n = s.length();

        // Create a stack and push -1 as initial index to it.
        Stack<Integer> stck = new Stack<Integer>();
        stck.push(-1);
        // Initialize res
        int res = 0;
        // Traverse all characters of given string
        for (int i=0; i<n; i++)
        {
            // If opening bracket, push index of it
            if(s.charAt(i) == '(')
              stck.push(i);

            else // If closing bracket, i.e.,s[i] = ')'
            {
                // Pop the previous opening bracket's index
                stck.pop();

                // Check if this length formed with base of
                // current valid substring is more than max 
                // so far
                if(stck.size()>0)
                    res = max(res, i - (Integer) stck.peek());
                // If stack is empty. push current index as 
                // base for next valid substring (if any)
                else stck.push(i);
            }
        }
        return res;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        System.out.println(maxLength(s));
    }
}

(()())((

Complexity Analysis for Length of Longest valid Substring

Time Complexity

O(n) where n is the size of the given string. Here we traverse while string char by char and perform some operations in constant time.

Space Complexity

O(n) because we use the stack. Here the maximum size of the stack will be n.