Find length of the longest valid parenthesis substring

Find length of the longest balanced parenthesis in a string.

---

Given a string consisting of opening and closing parenthesis, find the length of the longest balanced parenthesis in it.

Lets see sample input and output for better understanding:

longest valid parentheses count

Algorithm 

---

Approach 1:
Simple solution would be to take all the substring of the string and check whether it is valid or not. return the max length of balanced parenthesis.

Example: string ") ( ) )"
take all the substrings like,
i = 0 (starting from i=0 to n)

j=i to n
1. ")"
2. ") ("
3. ") ( )"
4. ") ( ) )"

i=1
j=i to n
5. "("
6. "( )"
7. "( ) )"

and so on.

At each step, calculate whether string is valid parenthesis using standard stack technique and if it is valid, max length at that point is string length.

Approach 2:

1. Initialize Stack with -1.
2. Iterate the String from i=0 to length.
3. When we encounter '(', we will push index i to stack.
4. When we encounter ')', this is the point we need to calculate length of longest balances parenthesis till this point.
 4.1. pop the element from the stack as this the matching parenthesis bracket ( )
 4.2  Subtract current index from index present at the peek of Stack, that is the max balanced parenthesis length till now.

Java Program to find length of the longest balanced parenthesis in a string

---

package com.javabypatel;

import java.util.Stack;

/**
    Input: (()()
    Output: 4
    Valid parenthesis string is ()(), length is 4

    Input: (((
    Output: 0
    No valid balanced parenthesis found.

    Input: (())()
    Output: 6
    Complete string has balanced parenthesis. length=6

    Input: ())(()
    Output: 2
    Balanced parenthesis is () at two occurrence, so max length is 2.

 */
public class LongestBalancedParenthesis {

    public static int getLongestValidParenthesesLength(String str) {
        Stack<Integer> indexes = new Stack<>();
        indexes.push(-1);

        int maxParenthesisSubstringLength = 0;
        int i = 0;
        while (i < str.length()) {
            if (str.charAt(i) == '(') {
                indexes.push(i);

            } else {
                indexes.pop();
                if (!indexes.isEmpty()) {
                    maxParenthesisSubstringLength = Math.max(maxParenthesisSubstringLength, i - indexes.peek());
                } else {
                    indexes.push(i);
                }
            }
            i++;
        }
        return maxParenthesisSubstringLength;
     }

    public static void main(String[] args) {
        String str = "())(()";
        System.out.println(getLongestValidParenthesesLength(str));
    }

}

You may also like to see

---

Sort Linked list using Merge sort

Bubble Sort

Heap Sort

Selection Sort

Insertion Sort

---

How ConcurrentHashMap works and ConcurrentHashMap interview questions

How Much Water Can A Bar Graph with different heights can Hold

Interview Questions-Answer Bank

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.