Open In App

Length of the longest valid substring

Last Updated : 22 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Given a string consisting of opening and closing parenthesis, find the length of the longest valid parenthesis substring.

Examples: 

Input: ((()
Output : 2
Explanation : ()
Input: )()())
Output : 4
Explanation: ()()
Input: ()(()))))
Output: 6
Explanation: ()(())
Recommended Practice

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

Time complexity of this solution is O(n3).
Space Complexity: O(1)

Approach 1 : The approach remains the same as Valid Parenthesis. The only hard part is to calculate the length. That can be done if the stack holds the indices of the not valid braces indices. Eg : “)()())” for this string the stack will hold the indices 0 and 5 as on these indices the braces are not valid.

Let’s get a quick run of the proposed algorithm:

1. at i = 0, open bracket so push the index 0. Stack contains: 0
2. at i = 1, open bracket so push the index 1. Stack contains: 0 1
3. at i = 2, closed bracket. Stack is not empty and on the top that is an index of open bracket. So pop. Stack contains only 0
4. at i = 3, again open and at i = 4 close bracket to again a push and then pop. Stack contains : 0
5. at i = 5, a close bracket. Stack is not empty but on top it’s a close bracket index. So push index 5. Stack contains : 0 5

Now if you see closely. These are the indices of the point where the not valid cases happen. Now in between these 2 indices there must be a valid string.
NOTE : it might happen that after the index 5, there is a valid string that won’t be in the stack to calculate. But it can easily be calculated if while popping out. Similarly on the left of index 0 there can be a valid string ( think given string “()() ) ()() )” to understand).

To handle the right side of index 5, “last” is initialized with N and on each iteration last is updated with now which is the current index. And to handle the left of index 0 (as mentioned) will return max(result, last). [ Cause if standing on index i, the length of the left part is i ]

So to find out the longest valid parenthesis these differences will contribute. To understand it better follow the below code :

C++
// C++ program to find length of the 
// longest valid substring
#include <bits/stdc++.h>
using namespace std;

int findMaxLen(string str)
{
    int n = str.length();

    // Create a stack
    stack<int> stk;

    // 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);
        
        // If closing bracket, i.e.,str[i] = ')'
        else
        {
            
            // If the stack is not empty and on the top
            // that is and index of a open bracket then pop
            if (!stk.empty() and str[stk.top()] == '(')
                stk.pop();

            // If stack is empty. push current index as
            // base for next valid substring (if any)
            else
                stk.push(i);
        }
    }

    // Initialize the result
    // 'last' is initialized
    // to calculate the distance
    int result = 0, last = n;


    while(!stk.empty())
    {
        int now = stk.top();
        stk.pop();

        // take the maximum in result
        result = max(result, last-now-1);

        // update the last index
        // with current index
        last = now;
    }

    // return the maximum of last and result
    return max(result, last);
}

// Driver code
int main()
{
    string str = "((()()";

    // Function call
    cout << findMaxLen(str) << endl;

    str = "()(()))))";

    // Function call
    cout << findMaxLen(str) << endl;

    return 0;
}
Java
import java.util.Stack;

public class Main {
    public static int findMaxLen(String str) {
        int n = str.length();
        
        // Create a stack
        Stack<Integer> stk = new Stack<>();
        
        // Traverse all characters of given string
        for (int i = 0; i < n; i++) {
            // If opening bracket, push index of it
            if (str.charAt(i) == '(')
                stk.push(i);
            // If closing bracket
            else {
                // If the stack is not empty and on the top
                // that is and index of an open bracket then pop
                if (!stk.isEmpty() && str.charAt(stk.peek()) == '(')
                    stk.pop();
                // If stack is empty, push current index as
                // base for next valid substring (if any)
                else
                    stk.push(i);
            }
        }

        // Initialize the result, 'last' is initialized
        // to calculate the distance
        int result = 0, last = n;

        while (!stk.isEmpty()) {
            int now = stk.pop();
            
            // take the maximum in result
            result = Math.max(result, last - now - 1);
            
            // update the last index with current index
            last = now;
        }

        // return the maximum of last and result
        return Math.max(result, last);
    }

    // Driver code
    public static void main(String[] args) {
        String str = "((()()";
        // Function call
        System.out.println(findMaxLen(str));

        str = "()(()))))";
        // Function call
        System.out.println(findMaxLen(str));
    }
}
Python
def find_max_len(s):
    n = len(s)  # Get the length of the input string
    stk = []  # Create an empty stack to store indices of '('
    result = 0  # Variable to store the maximum length of valid substring
    last = n    # Variable to keep track of the last index

    # Traverse the input string
    for i in range(n):
        if s[i] == '(':  # If current character is '('
            stk.append(i)  # Push its index onto the stack
        else:
            # If stack is not empty and top of stack contains '('
            if stk and s[stk[-1]] == '(':
                stk.pop()  # Pop the index of '(' from the stack
            else:
                # Push current index onto stack as base for next valid substring
                stk.append(i)

    # After traversing the string, calculate the length of longest valid substring
    while stk:
        now = stk.pop()  # Pop the index of '(' from stack
        # Calculate the length of valid substring
        result = max(result, last - now - 1)
        last = now  # Update last index

    # Return the maximum length of valid substring
    return max(result, last)


# Driver code
if __name__ == "__main__":
    s = "((()()"  # Test string 1
    # Output: 4 (Length of the longest valid substring is 4)
    print(find_max_len(s))

    s = "()(()))))"  # Test string 2
    # Output: 6 (Length of the longest valid substring is 6)
    print(find_max_len(s))
JavaScript
function GFG(str) {
    const n = str.length;
    // Create an array to act as a stack
    const stack = [];
    // Traverse all characters of the given string
    for (let i = 0; i < n; i++) {
        if (str[i] === '(')
            stack.push(i);
        else {
            // If the stack is not empty and on top
            // that is and index of the open bracket then pop
            if (stack.length && str[stack[stack.length - 1]] === '(')
                stack.pop();
            else
                stack.push(i);
        }
    }
    let result = 0, last = n;
    // Iterate through the stack to the calculate the maximum valid substring length
    while(stack.length) {
        const now = stack.pop();
        // take the maximum in the result
        result = Math.max(result, last - now - 1);
        last = now;
    }
    // Return the maximum of the last and result
    return Math.max(result, last);
}
// Driver code
const str1 = "((()()";
console.log(GFG(str1));
const str2 = "()(()))))";
console.log(GFG(str2));

Output
4
6
import java.util.Stack;

public class LongestValidParenthesis {

public static int longestValidParentheses(String s) {
int n = s.length();
Stack<Integer> stack = new Stack<>();
stack.push(-1); // Push -1 as a base index to handle the edge case when there's no valid prefix

int result = 0;
int last = -1; // To track the last not valid index

for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(i); // Push the index of opening parenthesis
} else {
stack.pop(); // Pop the index of matching opening parenthesis
if (stack.isEmpty()) {
stack.push(i); // Push the current index if stack is empty
} else {
// Calculate the length of valid substring
result = Math.max(result, i - stack.peek());
}
}
}

// If stack is not empty, calculate the length of valid substring from the last invalid index till the end
while (!stack.isEmpty()) {
int now = stack.pop();
result = Math.max(result, last - now);
last = now; // Update the last not valid index
}

return result;
}

public static void main(String[] args) {
String[] testCases = {"((()", ")()())", "()(()))))"};

for (String testCase : testCases) {
System.out.println("Longest valid parenthesis for \"" + testCase + "\": " + longestValidParentheses(testCase));
}
}
}

Time Complexity: O(N), here N is the length of string.
Auxiliary Space: O(N)

In the previous approach without using 2 different loops the whole approach can also be done in a single loop.

Below is the implementation of the above algorithm. 

C++
// C++ program to find length of the 
// longest valid substring
#include <bits/stdc++.h>
using namespace std;

int findMaxLen(string str)
{
    int n = str.length();

    // Create a stack and 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);
        
        // If closing bracket, i.e.,str[i] = ')'
        else 
        {
            // Pop the previous opening
            // bracket's index
            if (!stk.empty()) 
            {
                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;
}

// Driver code
int main()
{
    string str = "((()()";
  
    // Function call
    cout << findMaxLen(str) << endl;

    str = "()(()))))";
  
    // Function call
    cout << findMaxLen(str) << endl;

    return 0;
}
Java
// Java program to find length of the longest valid
// substring

import java.util.Stack;

class Test 
{
    // method to get length of the longest valid
    static int findMaxLen(String str)
    {
        int n = str.length();

        // Create a stack and push -1 
        // as initial index to it.
        Stack<Integer> stk = new Stack<>();
        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.charAt(i) == '(')
                stk.push(i);

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

                // Check if this length 
                // formed with base of
                // current valid substring 
                // is more than max
                // so far
                if (!stk.empty())
                    result
                        = Math.max(result, 
                                   i - stk.peek());

                // If stack is empty. push 
                // current index as base 
                // for next valid substring (if any)
                else
                    stk.push(i);
            }
        }

        return result;
    }

    // Driver code
    public static void main(String[] args)
    {
        String str = "((()()";
      
        // Function call
        System.out.println(findMaxLen(str));

        str = "()(()))))";
      
        // Function call
        System.out.println(findMaxLen(str));
    }
}
Python3
# Python program to find length of the longest valid
# substring


def findMaxLen(string):
    n = len(string)

    # Create a stack and push -1
    # as initial index to it.
    stk = []
    stk.append(-1)

    # Initialize result
    result = 0

    # Traverse all characters of given string
    for i in range(n):

        # If opening bracket, push index of it
        if string[i] == '(':
            stk.append(i)
        
        # If closing bracket, i.e., str[i] = ')'
        else:

            # Pop the previous opening bracket's index
            if len(stk) != 0:
                stk.pop()

            # Check if this length formed with base of
            # current valid substring is more than max
            # so far
            if len(stk) != 0:
                result = max(result,
                            i - stk[len(stk)-1])

            # If stack is empty. push current index as
            # base for next valid substring (if any)
            else:
                stk.append(i)

    return result


# Driver code
string = "((()()"

# Function call
print (findMaxLen(string))

string = "()(()))))"

# Function call
print (findMaxLen(string))

# This code is contributed by Bhavya Jain

# This code is modified by Susobhan Akhuli
C#
// C# program to find length of
// the longest valid substring
using System;
using System.Collections.Generic;

class GFG {
    // method to get length of
    // the longest valid
    public static int findMaxLen(string str)
    {
        int n = str.Length;

        // Create a stack and push -1 as
        // initial index to it.
        Stack<int> stk = new Stack<int>();
        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
                if (stk.Count > 0)
                    stk.Pop();

                // Check if this length formed
                // with base of current valid
                // substring is more than max
                // so far
                if (stk.Count > 0) 
                {
                    result
                        = Math.Max(result, 
                                   i - stk.Peek());
                }

                // If stack is empty. push current
                // index as base for next valid
                // substring (if any)
                else {
                    stk.Push(i);
                }
            }
        }

        return result;
    }

    // Driver Code
    public static void Main(string[] args)
    {
        string str = "((()()";
      
        // Function call
        Console.WriteLine(findMaxLen(str));

        str = "()(()))))";
      
        // Function call
        Console.WriteLine(findMaxLen(str));
    }
}

// This code is contributed by Shrikant13
JavaScript
 <script>
        // JavaScript Program for the above approach
        function findMaxLen(str)
        {
            let n = str.length;

            // Create a stack and push -1 as 
            // initial index to it.
            let stk = [];
            stk.push(-1);

            // Initialize result
            let result = 0;

            // Traverse all characters of given string
            for (let i = 0; i < n; i++)
            {
                // If opening bracket, push index of it
                if (str.charAt(i) == '(') 
                {
                    stk.push(i);
                }
                
                // If closing bracket, i.e.,str[i] = ')'
                else
                {
                    // Pop the previous opening
                    // bracket's index
                    if (stk.length != 0) {
                        stk.pop();
                    }

                    // Check if this length formed with base of
                    // current valid substring is more than max
                    // so far
                    if (stk.length != 0) {
                        result = Math.max(result, i - stk[stk.length - 1]);
                    }
                    
                    // If stack is empty. push current index as
                    // base for next valid substring (if any)
                    else {
                        stk.push(i);
                    }
                }
            }

            return result;
        }

        // Driver code
        let str = "((()()";

        // Function call
        document.write(findMaxLen(str) + "<br>");

        str = "()(()))))";

        // Function call
        document.write(findMaxLen(str) + "<br>");

    // This code is contributed by Potta Lokesh
    </script>

Output
4
6

Time Complexity: O(N), here N is the length of string.
Auxiliary Space: O(N)

Explanation with example: 

Input: str = "(()()"
Initialize result as 0 and stack with one item -1.
For i = 0, str[0] = '(', we push 0 in stack
For i = 1, str[1] = '(', we push 1 in stack
For i = 2, str[2] = ')', currently stack has
[-1, 0, 1], we pop from the stack and the stack
now is [-1, 0] and length of current valid substring
becomes 2 (we get this 2 by subtracting stack top from
current index).
Since the current length is more than the current result,
we update the result.
For i = 3, str[3] = '(', we push again, stack is [-1, 0, 3].
For i = 4, str[4] = ')', we pop from the stack, stack
becomes [-1, 0] and length of current valid substring
becomes 4 (we get this 4 by subtracting stack top from
current index).
Since current length is more than current result,
we update result.


Another Efficient Approach can solve the problem in O(N) time. The idea is to maintain an array that stores the length of the longest valid substring ending at that index. We iterate through the array and return the maximum value.

Below is the implementations of the above algorithm.

C++
// C++ program to find length of the longest valid
// substring
#include <bits/stdc++.h>
using namespace std;

int findMaxLen(string s)
{
    if (s.length() <= 1)
        return 0;

    // Initialize curMax to zero
    int curMax = 0;

    vector<int> longest(s.size(), 0);

    // Iterate over the string starting from second index
    for (int i = 1; i < s.length(); i++) 
    {
        if (s[i] == ')' && i - longest[i - 1] - 1 >= 0
            && s[i - longest[i - 1] - 1] == '(') 
        {
            longest[i]
                = longest[i - 1] + 2
                  + ((i - longest[i - 1] - 2 >= 0)
                  ? longest[i - longest[i - 1] - 2]
                  : 0);
            curMax = max(longest[i], curMax);
        }
    }
    return curMax;
}

// Driver code
int main()
{
    string str = "((()()";
  
    // Function call
    cout << findMaxLen(str) << endl;

    str = "()(()))))";
  
    // Function call
    cout << findMaxLen(str) << endl;

    return 0;
}
// This code is contributed by Vipul Lohani
Java
// Java program to find length of the longest valid
// subString
import java.util.*;
class GFG
{

  static int findMaxLen(String s)
  {
    if (s.length() <= 1)
      return 0;

    // Initialize curMax to zero
    int curMax = 0;
    int[] longest = new int[s.length()];

    // Iterate over the String starting from second index
    for (int i = 1; i < s.length(); i++) 
    {
      if (s.charAt(i) == ')' && i - longest[i - 1] - 1 >= 0
          && s.charAt(i - longest[i - 1] - 1) == '(') 
      {
        longest[i]
          = longest[i - 1] + 2
          + ((i - longest[i - 1] - 2 >= 0)
             ? longest[i - longest[i - 1] - 2]
             : 0);
        curMax = Math.max(longest[i], curMax);
      }
    }
    return curMax;
  }

  // Driver code
  public static void main(String[] args)
  {
    String str = "((()()";

    // Function call
    System.out.print(findMaxLen(str) +"\n");

    str = "()(()))))";

    // Function call
    System.out.print(findMaxLen(str) +"\n");

  }
}

// This code is contributed by aashish1995 
Python3
# Python3 program to find length of
# the longest valid substring


def findMaxLen(s):
    if (len(s) <= 1):
        return 0

    # Initialize curMax to zero
    curMax = 0

    longest = [0] * (len(s))

    # Iterate over the string starting
    # from second index
    for i in range(1, len(s)):
        if ((s[i] == ')' 
             and i - longest[i - 1] - 1 >= 0 
             and s[i - longest[i - 1] - 1] == '(')):
            
            longest[i] = longest[i - 1] + 2
            if (i - longest[i - 1] - 2 >= 0):
                longest[i] += (longest[i -
                                       longest[i - 1] - 2])
            else:
                longest[i] += 0
            curMax = max(longest[i], curMax)
    return curMax


# Driver Code
if __name__ == '__main__':
    Str = "((()()"
    
    # Function call
    print(findMaxLen(Str))

    Str = "()(()))))"
    
    # Function call
    print(findMaxLen(Str))

# This code is contributed by PranchalK
C#
// C# program to find length of the longest valid
// subString
using System;

public class GFG {

    static int findMaxLen(String s) {
        if (s.Length <= 1)
            return 0;

        // Initialize curMax to zero
        int curMax = 0;
        int[] longest = new int[s.Length];

        // Iterate over the String starting from second index
        for (int i = 1; i < s.Length; i++) {
            if (s[i] == ')' && i - longest[i - 1] - 1 >= 0 && s[i - longest[i - 1] - 1] == '(') {
                longest[i] = longest[i - 1] + 2 + ((i - longest[i - 1] - 2 >= 0) ? longest[i - longest[i - 1] - 2] : 0);
                curMax = Math.Max(longest[i], curMax);
            }
        }
        return curMax;
    }

    // Driver code
    public static void Main(String[] args) {
        String str = "((()()";

        // Function call
        Console.Write(findMaxLen(str) + "\n");

        str = "()(()))))";

        // Function call
        Console.Write(findMaxLen(str) + "\n");
    }
}

// This code is contributed by aashish1995
JavaScript
<script>
// javascript program to find length of the longest valid
// subString
    function findMaxLen( s) {
        if (s.length <= 1)
            return 0;

        // Initialize curMax to zero
        var curMax = 0;
        var longest = Array(s.length).fill(0);

        // Iterate over the String starting from second index
        for (var i = 1; i < s.length; i++) {
            if (s[i] == ')' && i - longest[i - 1] - 1 >= 0 && s[i - longest[i - 1] - 1] == '(') {
                longest[i] = longest[i - 1] + 2 + ((i - longest[i - 1] - 2 >= 0) ? longest[i - longest[i - 1] - 2] : 0);
                curMax = Math.max(longest[i], curMax);
            }
        }
        return curMax;
    }

    // Driver code
        var str = "((()()";

        // Function call
        document.write(findMaxLen(str) + "<br\>");

        str = "()(()))))";

        // Function call
        document.write(findMaxLen(str) + "<br\>");

// This code is contributed by umadevi9616 
</script>

Output
4
6

Time Complexity: O(N), here N is the length of string.
Auxiliary Space: O(N)

Another approach in O(1) auxiliary space and O(N) Time complexity: 

  1. The idea to solve this problem is to traverse the string on and keep track of the count of open parentheses and close parentheses with the help of two counters left and right respectively.
  2. First, the string is traversed from the left towards the right and for every “(” encountered, the left counter is incremented by 1 and for every “)” the right counter is incremented by 1.
  3. Whenever the left becomes equal to right, the length of the current valid string is calculated and if it greater than the current longest substring, then value of required longest substring is updated with current string length.
  4. If the right counter becomes greater than the left counter, then the set of parentheses has become invalid and hence the left and right counters are set to 0.
  5. After the above process, the string is similarly traversed from right to left and similar procedure is applied.

Below is the implementation of the above approach: 

C++
#include <bits/stdc++.h>
using namespace std;

// Function to return the length of
// the longest valid substring
int solve(string s, int n)
{

    // Variables for left and right counter.
    // maxlength to store the maximum length found so far
    int left = 0, right = 0, maxlength = 0;

    // Iterating the string from left to right
    for (int i = 0; i < n; i++) {
        // If "(" is encountered,
        // then left counter is incremented
        // else right counter is incremented
        if (s[i] == '(')
            left++;
        else
            right++;

        // Whenever left is equal to right, it signifies
        // that the subsequence is valid and
        if (left == right)
            maxlength = max(maxlength, 2 * right);

        // Resetting the counters when the subsequence
        // becomes invalid
        else if (right > left)
            left = right = 0;
    }

    left = right = 0;

    // Iterating the string from right to left
    for (int i = n - 1; i >= 0; i--) {

        // If "(" is encountered,
        // then left counter is incremented
        // else right counter is incremented
        if (s[i] == '(')
            left++;
        else
            right++;

        // Whenever left is equal to right, it signifies
        // that the subsequence is valid and
        if (left == right)
            maxlength = max(maxlength, 2 * left);

        // Resetting the counters when the subsequence
        // becomes invalid
        else if (left > right)
            left = right = 0;
    }
    return maxlength;
}

// A much shorter and concise version of the above code
int solve2(string s, int n)
{
    int left = 0, right = 0, maxlength = 0, t = 2;
    while (t--) {
        left = 0;
        right = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '(')
                left++;
            else
                right++;

            if (left == right) {
                maxlength = max(maxlength, 2 * left);
            }
            // when travelling from 0 to n-1
            if (t % 2 == 1 && right > left) {
                left = 0;
                right = 0;
            }
            // when travelling from n-1 to 0
            if (t % 2 == 0 && left > right) {
                left = 0;
                right = 0;
            }
        }
        // now we need to do the same thing from the other
        // side;
        reverse(s.begin(), s.end());
    }
    return maxlength;
}

// Driver code
int main()
{
    // Function call
    string str = "((()()()()(((())";
    cout << solve(str, str.length());
    return 0;
}
Java
import java.util.Scanner;
import java.util.Arrays;

class GFG {

    // Function to return the length
    // of the longest valid substring
    public static int solve(String s, int n)
    {

        // Variables for left and right
        // counter maxlength to store
        // the maximum length found so far
        int left = 0, right = 0;
        int maxlength = 0;

        // Iterating the string from left to right
        for (int i = 0; i < n; i++) {

            // If "(" is encountered, then
            // left counter is incremented
            // else right counter is incremented
            if (s.charAt(i) == '(')
                left++;
            else
                right++;

            // Whenever left is equal to right,
            // it signifies that the subsequence
            // is valid and
            if (left == right)
                maxlength = Math.max(maxlength,
                                     2 * right);

            // Resetting the counters when the
            // subsequence becomes invalid
            else if (right > left)
                left = right = 0;
        }

        left = right = 0;

        // Iterating the string from right to left
        for (int i = n - 1; i >= 0; i--) {

            // If "(" is encountered, then
            // left counter is incremented
            // else right counter is incremented
            if (s.charAt(i) == '(')
                left++;
            else
                right++;

            // Whenever left is equal to right,
            // it signifies that the subsequence
            // is valid and
            if (left == right)
                maxlength = Math.max(maxlength, 
                                     2 * left);

            // Resetting the counters when the
            // subsequence becomes invalid
            else if (left > right)
                left = right = 0;
        }
        return maxlength;
    }

    // Driver code
    public static void main(String args[])
    {
          String str = "((()()()()(((())";
        // Function call
        System.out.print(solve(str, str.length()));
    }
}
Python3
# Python3 program to implement the above approach

# Function to return the length of
# the longest valid substring


def solve(s, n):

    # Variables for left and right counter.
    # maxlength to store the maximum length found so far
    left = 0
    right = 0
    maxlength = 0

    # Iterating the string from left to right
    for i in range(n):

        # If "(" is encountered,
        # then left counter is incremented
        # else right counter is incremented
        if (s[i] == '('):
            left += 1
        else:
            right += 1

        # Whenever left is equal to right, it signifies
        # that the subsequence is valid and
        if (left == right):
            maxlength = max(maxlength, 2 * right)

        # Resetting the counters when the subsequence
        # becomes invalid
        elif (right > left):
            left = right = 0

    left = right = 0

    # Iterating the string from right to left
    for i in range(n - 1, -1, -1):

        # If "(" is encountered,
        # then left counter is incremented
        # else right counter is incremented
        if (s[i] == '('):
            left += 1
        else:
            right += 1

        # Whenever left is equal to right, it signifies
        # that the subsequence is valid and
        if (left == right):
            maxlength = max(maxlength, 2 * left)

        # Resetting the counters when the subsequence
        # becomes invalid
        elif (left > right):
            left = right = 0
    return maxlength


# Driver code
# Function call
s = "((()()()()(((())"
print(solve(s, len(s)))
C#
// C# program to implement the above approach
using System;

public class GFG {

  // Function to return the length
  // of the longest valid substring
  public static int solve(String s, int n)
  {

    // Variables for left and right
    // counter maxlength to store
    // the maximum length found so far
    int left = 0, right = 0;
    int maxlength = 0;

    // Iterating the string from left to right
    for (int i = 0; i < n; i++) {

      // If "(" is encountered, then
      // left counter is incremented
      // else right counter is incremented
      if (s[i] == '(')
        left++;
      else
        right++;

      // Whenever left is equal to right,
      // it signifies that the subsequence
      // is valid and
      if (left == right)
        maxlength = Math.Max(maxlength,
                             2 * right);

      // Resetting the counters when the
      // subsequence becomes invalid
      else if (right > left)
        left = right = 0;
    }

    left = right = 0;

    // Iterating the string from right to left
    for (int i = n - 1; i >= 0; i--) {

      // If "(" is encountered, then
      // left counter is incremented
      // else right counter is incremented
      if (s[i] == '(')
        left++;
      else
        right++;

      // Whenever left is equal to right,
      // it signifies that the subsequence
      // is valid and
      if (left == right)
        maxlength = Math.Max(maxlength, 
                             2 * left);

      // Resetting the counters when the
      // subsequence becomes invalid
      else if (left > right)
        left = right = 0;
    }
    return maxlength;
  }

  // Driver code
  public static void Main(String []args)
  {
    String str = "((()()()()(((())";
    // Function call
    Console.Write(solve(str, str.Length));
  }
}
JavaScript
// Function to return the length of
// the longest valid substring
function solve(s, n) {
    let left = 0, right = 0, maxlength = 0;

    // Iterating the string from left to right
    for (let i = 0; i < n; i++) {
        if (s[i] === '(')
            left++;
        else
            right++;

        if (left === right)
            maxlength = Math.max(maxlength, 2 * right);
        else if (right > left)
            left = right = 0;
    }

    left = right = 0;

    // Iterating the string from right to left
    for (let i = n - 1; i >= 0; i--) {
        if (s[i] === '(')
            left++;
        else
            right++;

        if (left === right)
            maxlength = Math.max(maxlength, 2 * left);
        else if (left > right)
            left = right = 0;
    }
    return maxlength;
}

// A much shorter and concise version of the above code
function solve2(s, n) {
    let left = 0, right = 0, maxlength = 0;
    for (let t = 0; t < 2; t++) {
        left = 0;
        right = 0;
        for (let i = 0; i < n; i++) {
            if (s[i] === '(') left++;
            else right++;

            if (left === right) maxlength = Math.max(maxlength, 2 * left);

            if ((t % 2 === 1 && right > left) || (t % 2 === 0 && left > right)) {
                left = 0;
                right = 0;
            }
        }
        // now we need to do the same thing from the other side;
        s = s.split('').reverse().join('');
    }
    return maxlength;
}

// Driver code
let str = "((()()()()(((())";
console.log(solve(str, str.length));

Output
8

Time Complexity: O(N), here N is the length of string.
Auxiliary Space: O(1)

Another Approach (Using Memoization):

Intuition:
The problem statement is asking for the length of the longest valid parentheses substring. One way to think about this problem is that for every ‘(‘ we encounter, we need a corresponding ‘)’ somewhere else in the string to form a valid parentheses pair. Therefore, a valid substring must start with an ‘(‘ and end with a ‘)’, and any number of valid parentheses pairs can be in between.

Approach:
The approach used here is to use a stack to keep track of the indexes of the characters in the input string. When a ‘(‘ character is encountered, its index is pushed onto the stack. When a ‘)’ character is encountered, the top index on the stack is popped. The difference between the current index and the top index on the stack represents the length of a valid substring ending at the current index. If the stack is empty after a ‘)’ is popped, it means that no matching ‘(‘ has been found, so the current index is pushed onto the stack as the new base for future valid substrings. By doing so, the solution keeps track of the potential valid parentheses starts and ends, and makes use of the property that any valid parentheses substring must be closed by an earlier opened one. Finally, the algorithm returns the max length at the end of the loop.

Idea : try to break in smaller sub problem .
case 1: string ends at “()”
longestParenEnding(0, i) = longestParenEnding(0, i – 2) + 2

case 2: string ends with “))” for example “()(())”
longestParenEnding(0, i) =

case 3: string ends with “(“
longestParenEnding(0, i) = 0

Below is the implementation of the above approach: 

C++
// C++ program to implement the above approach

#include <bits/stdc++.h>
using namespace std;

// Function to return the length of
// the longest valid substring
int lonParen(int i, string& s, vector<int>& memo)
{
    // base condition
    if (i <= 0) {
        return 0;
    }
    // checking if value already present in the dp array
    if (memo[i] != -1) {
        return memo[i];
    }
    // check for beginning bracket
    if (s[i] == '(') {
        memo[i] = 0;
    } // check if beginning and ending brackets satisfy
    else if (s[i] == ')' && s[i - 1] == '(') {
        memo[i] = lonParen(i - 2, s, memo) + 2;
    }
    // check if the bracket at the ith position is same as
    // bracket at i-1th position
    else if (s[i] == ')' && s[i - 1] == ')') {
        int len = lonParen(i - 1, s, memo);
        if (i - 1 - len >= 0 && s[i - 1 - len] == '(') {
            memo[i]
                = len + 2 + lonParen(i - len - 2, s, memo);
        }
        else {
            // if none of the condition satisfy store 0 in
            // the dp array
            memo[i] = 0;
        }
    }
    // return the value at the last index
    return memo[i];
}

int longestValidParentheses(string s)
{

    int n = s.size(), maxLen = 0;
    // dp vector for storing the results
    vector<int> memo(n, -1);
    // getting the maximum length
    for (int i = 0; i < n; i++) {
        maxLen = max(maxLen, lonParen(i, s, memo));
    }
    // return the maximum length
    return maxLen;
}
// Driver code
int main()
{

    // Function call
    cout << longestValidParentheses("((()()()()(((())");
    return 0;
}
Java
import java.util.Arrays;

public class Main {
    // Function to return the length of the longest valid substring
    public static int longestValidParentheses(String s) {
        int n = s.length();
        int maxLen = 0;
        int[] memo = new int[n];
        Arrays.fill(memo, -1);

        // Iterate through each character in the input string
        for (int i = 0; i < n; i++) {
            // Update maxLen with the maximum length of valid parentheses encountered so far
            maxLen = Math.max(maxLen, lonParen(i, s, memo));
        }

        return maxLen;  // Return the length of the longest valid substring
    }

    // Function to calculate the length of the longest valid parentheses substring ending at index i
    public static int lonParen(int i, String s, int[] memo) {
        if (i <= 0) {
            return 0;  // If index i is less than or equal to 0, the substring cannot be valid
        }

        if (memo[i] != -1) {
            return memo[i];  // If the length has already been memoized, return the memoized value
        }

        if (s.charAt(i) == '(') {
            memo[i] = 0;  // If the current character is '(', the substring cannot be valid
        } else if (s.charAt(i) == ')' && s.charAt(i - 1) == '(') {
            // If the current character is ')' and the previous character is '(', we have a valid pair
            // The length of the valid substring ending at index i is the length of the valid substring ending at index i-2 plus 2
            memo[i] = lonParen(i - 2, s, memo) + 2;
        } else if (s.charAt(i) == ')' && s.charAt(i - 1) == ')') {
            // If the current character is ')' and the previous character is ')'
            // We need to check if there is a valid substring ending at index i-1
            int len = lonParen(i - 1, s, memo);
            if (i - 1 - len >= 0 && s.charAt(i - 1 - len) == '(') {
                // If there is a valid substring ending at index i-1 and the character before it is '(', we have a valid pair
                // The length of the valid substring ending at index i is the length of the valid substring ending at index i-1
                // plus 2 plus the length of the valid substring ending at index i-len-2
                memo[i] = len + 2 + lonParen(i - len - 2, s, memo);
            } else {
                memo[i] = 0;  // If there is no valid substring ending at index i-1, the substring cannot be valid
            }
        }

        return memo[i];  // Return the length of the longest valid parentheses substring ending at index i
    }

    public static void main(String[] args) {
        System.out.println(longestValidParentheses("((()()()()(((())"));  // Test the function with an example input
    }
}
Python3
def lonParen(i, s, memo):
    # base condition
    if i <= 0:
        return 0
    
    # checking if value already present in the dp array
    if memo[i] != -1:
        return memo[i]

    # check for beginning bracket
    if s[i] == '(':
        memo[i] = 0
    # check if beginning and ending brackets satisfy
    elif s[i] == ')' and s[i - 1] == '(':
        memo[i] = lonParen(i - 2, s, memo) + 2
    # check if the bracket at the ith position is same as
    # bracket at i-1th position
    elif s[i] == ')' and s[i - 1] == ')':
        length = lonParen(i - 1, s, memo)
        if i - 1 - length >= 0 and s[i - 1 - length] == '(':
            memo[i] = length + 2 + lonParen(i - length - 2, s, memo)
        else:
            # if none of the condition satisfy store 0 in
            # the dp array
            memo[i] = 0

    # return the value at the last index
    return memo[i]


def longestValidParentheses(s):
    n = len(s)
    maxLen = 0

    # dp list for storing the results
    memo = [-1] * n
    
    # getting the maximum length
    for i in range(n):
        maxLen = max(maxLen, lonParen(i, s, memo))
    
    # return the maximum length
    return maxLen


# Driver code
print(longestValidParentheses("((()()()()(((())"))
C#
using System;

class Program
{
    // Function to return the length of the longest valid substring
    static int LongestValidParentheses(int i, string s, int[] memo)
    {
        // Base condition
        if (i <= 0)
        {
            return 0;
        }

        // Checking if value already present in the memo array
        if (memo[i] != -1)
        {
            return memo[i];
        }

        // Check for beginning bracket
        if (s[i] == '(')
        {
            memo[i] = 0;
        }
        // Check if beginning and ending brackets satisfy
        else if (s[i] == ')' && s[i - 1] == '(')
        {
            memo[i] = LongestValidParentheses(i - 2, s, memo) + 2;
        }
        // Check if the bracket at the ith position is the same as the bracket at i-1th position
        else if (s[i] == ')' && s[i - 1] == ')')
        {
            int len = LongestValidParentheses(i - 1, s, memo);
            if (i - 1 - len >= 0 && s[i - 1 - len] == '(')
            {
                memo[i] = len + 2 + LongestValidParentheses(i - len - 2, s, memo);
            }
            else
            {
                // If none of the conditions satisfy, store 0 in the memo array
                memo[i] = 0;
            }
        }

        // Return the value at the last index
        return memo[i];
    }

    static int LongestValidParentheses(string s)
    {
        int n = s.Length, maxLen = 0;

        // Memo array for storing the results
        int[] memo = new int[n];
        for (int i = 0; i < n; i++)
        {
            memo[i] = -1;
        }

        // Getting the maximum length
        for (int i = 0; i < n; i++)
        {
            maxLen = Math.Max(maxLen, LongestValidParentheses(i, s, memo));
        }

        // Return the maximum length
        return maxLen;
    }

    // Driver code
    static void Main()
    {
        // Function call
        Console.WriteLine(LongestValidParentheses("((()()()()(((())"));
    }
}
JavaScript
function lonParen(i, s, memo) {
    // Base condition
    if (i <= 0) {
        return 0;
    }

    // Checking if value already present in the memo array
    if (memo[i] !== -1) {
        return memo[i];
    }

    // Check for beginning bracket
    if (s.charAt(i) === '(') {
        memo[i] = 0;
    }
    // Check if beginning and ending brackets satisfy
    else if (s.charAt(i) === ')' && s.charAt(i - 1) === '(') {
        memo[i] = lonParen(i - 2, s, memo) + 2;
    }
    // Check if the bracket at the ith position is the same as
    // the bracket at i-1th position
    else if (s.charAt(i) === ')' && s.charAt(i - 1) === ')') {
        let length = lonParen(i - 1, s, memo);
        if (i - 1 - length >= 0 && s.charAt(i - 1 - length) === '(') {
            memo[i] = length + 2 + lonParen(i - length - 2, s, memo);
        } else {
            // If none of the conditions satisfy, store 0 in the memo array
            memo[i] = 0;
        }
    }

    // Return the value at the last index
    return memo[i];
}

function longestValidParentheses(s) {
    let n = s.length;
    let maxLen = 0;

    // Memo array for storing the results
    let memo = Array(n).fill(-1);

    // Getting the maximum length
    for (let i = 0; i < n; i++) {
        maxLen = Math.max(maxLen, lonParen(i, s, memo));
    }

    // Return the maximum length
    return maxLen;
}

// Driver code
console.log(longestValidParentheses("((()()()()(((())"));

Output
8

Time complexity: O(n),Here, The algorithm has a time complexity of O(n) because it simply iterates the string once.
Auxiliary Space: O(n),Space complexity is O(n) because it uses a stack to keep track of the indexes of the characters in the input string.



Previous Article
Next Article

Similar Reads

Find a valid parenthesis sequence of length K from a given valid parenthesis sequence
Given a string S of valid parentheses sequence of length N and an even integer K, the task is to find the valid parentheses sequence of length K which is also a subsequence of the given string. Note: There can be more than one valid sequence, print any of them. Examples: Input: S = "()()()", K = 4Output: ()()Explanation:The string "()()" is a subse
7 min read
Generate an N-length string having longest palindromic substring of length K
Given two integers N and K (K ? N), the task is to obtain a string of length N such that maximum length of a palindromic substring of this string is K. Examples: Input: N = 5, K = 3 Output: "abacd" Explanation: Palindromic substrings are "a", "b", "c", "d" and "aba". Therefore, the longest palindromic substring from the given string is of length 3.
4 min read
Check valid Substring of at least k length
Given a string s ('a' &lt;= s[i] &lt;= 'z') and an integer k (1 &lt;= k &lt; n &lt;= 105), the task is to check if any valid substrings of at least k length exist in the given string. A substring is valid if the occurrences of each character in the substring should be even. Examples: Input: s = “bba”, k = 2Output: trueExplanation: Below is valid su
5 min read
Find the length of the longest valid number chain in an Array
Given an array A[] of N numbers, the task is to find the length of the longest valid number that can be formed by connecting one or more numbers from the array such that, while connecting two numbers the last digit of the previous number is the same as the first digit of the next number. Examples: Input: A = [100, 234, 416, 654, 412, 298, 820, 177]
10 min read
Longest substring whose any non-empty substring not prefix or suffix of given String
Given a string S of length N, the task is to find the length of the longest substring X of the string S such that: No non-empty substring of X is a prefix of S.No non-empty substring of X is a suffix of S.If no such string is possible, print −1. Examples: Input: S = "abcdefb"Output: 4Explanation: cdef is the substring satisfying the conditions. Inp
5 min read
Longest Substring of A that can be changed to Substring of B in at most T cost
Given two strings A and B of the same length and two positive integers K and T. The task is to find the longest substring of A that can be converted to the same substring at the same position in B in less than or equal to T cost. Converting any character of A to any other character costs K units. Note: If multiple valid substrings are possible then
13 min read
Length of the largest substring which have character with frequency greater than or equal to half of the substring
Given a string S consisting of characters from 'a' to 'z'. The task is to find the length of the largest substring of S which contains a character whose frequency in the sub-string is greater than or equal to half of the length of the substring.Note: For odd-length substring, to calculate half-length consider integer division. For example, half of
10 min read
Minimum length of substring whose rotation generates a palindromic substring
Given a string str, the task is to find the minimum length of substring required to rotate that generates a palindromic substring from the given string. Examples: Input: str = "abcbd" Output: 0 Explanation: No palindromic substring can be generated. There is no repeated character in the string. Input: str = "abcdeba" Output: 3 Explanation: Rotate s
7 min read
Length of the longest substring with consecutive characters
Given string str of lowercase alphabets, the task is to find the length of the longest substring of characters in alphabetical order i.e. string "dfabck" will return 3. Note that the alphabetical order here is considered circular i.e. a, b, c, d, e, ..., x, y, z, a, b, c, .... Examples: Input: str = "abcabcdefabc" Output: 6 All valid sub-strings ar
7 min read
Length of the longest substring that do not contain any palindrome
Given a string of lowercase, find the length of the longest substring that does not contain any palindrome as a substring. Examples: Input : str = "daiict" Output : 3 dai, ict are longest substring that do not contain any palindrome as substring Input : str = "a" Output : 0 a is itself a palindrome The idea is to observe that if any character forms
6 min read
three90RightbarBannerImg