Code 101: Longest Valid Parentheses ( LeetCode Hard Problem )

Question:

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

 

Example 1:

Input: s = "(()" Output: 2 Explanation: The longest valid parentheses substring is "()". 

Example 2:

Input: s = ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()". 

Example 3:

Input: s = "" Output: 0 

 

Constraints:

• 0 <= s.length <= 3 * 104
• s[i] is '(', or ')'.

You can find the question here.

Solution:

Stack Approach

First thing whenever I see questions that have something to balance, validate, or format, I think in terms of the stack. The first thought is to check can we solve this with the stack.

Coming to the problem, How do we say a parenthesis is valid? Whenever we see 1 closing and corresponding opening parenthesis.

How do we say a parenthesis is invalid? Whenever we see a closing parenthesis without an opening parenthesis. We cannot say the same for the opening parenthesis because we can say that in the future a closing parenthesis might come.

Also, we need to find the longest valid string length, so we need to maintain the size some place.

Now with this information, we can derive an algorithm to solve this.

Let's say we iterate the string and

1. Whenever we encounter '(' we add it's index to the stack.
2. Whenever we encounter ')' now we need to check if there is any valid combination to add to out result or not.
3. To calculate max length we need to check the index with the index of the '(' which will be present in the stack top.
4. There are a few scenarios that are missed above.
5. What happens when there is String "()" -> result would be 1 instead of 2
6. What if we have more ')', That means we have an invalid string starting. So now we need to restart our calculation. We will do that by adding the index of the invalid string start
7. Edge case: only ')'

I have added inline comments in the code for a better understanding of the algorithm.

import java.util.Stack;

public class LongestValidParenthesis {
    public static int longestValidParentheses(String s) {
        int res = 0; // Initial length
        Stack<Integer> st = new Stack<>(); // Initialize the stack
        st.push(-1); // Added to handle edge case
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                st.push(i);
            } else {
                if (st.size() > 1 && s.charAt(st.peek()) == '(') {
                    st.pop();
                    res = Math.max(res,i - st.peek()); // calc the length of valid string
                } else {
                    st.push(i); // To handle invalid scenarios 
                }
            }
        }
        return res;
    }

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

Above is 1 approach to solve this question. Once I understood this, I wanted to check what all other solutions could be possible for this question.

I found there are 2 more ways to solve this.

1. Dynamic Programing
2. Without extra space

Dynamic Programming Approach

Dp problems consist of 2 parts, 1st subproblem, and 2nd memoization.

The condition for valid and invalid remains the same for every approach. So now the subproblem will be something when we have ) do we have corresponding ( and we will maintain the length of each valid substring.

The below code demonstrates the same algo, I have added inline comments for better understanding.

public class LongestValidParenthesis {

    public static int longestValidParenthesesDP(String str) {
        int res = 0;
        int dp[] = new int[str.length()];
        for (int i = 1; i < str.length(); i++) {
            if (str.charAt(i) == ')') { // Whenever we encounter ')'
                if (str.charAt(i - 1) == '(') { // We need to check if the character before is '(' or not
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; // if true we just add 2 to the previously calculated length of valid substring
                } else if (i - dp[i - 1] > 0 && str.charAt(i - dp[i - 1] - 1) == '(') {
                    // i - dp[i-1] -1 means we are pointing to the index just before we had a valid string,
                    // because the dp[i-1] has the valid substring length
                    // once we at that index we need to check that the index is having '('
                    // this means we have addition to our valid substring
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }

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

Without Extra Space

This solution I did not think, I just read it from the solution and find it interesting so thought to add it.

Here the idea remains the same, only now we use 2 pointers and we traverse 2 times, 1 left to right & 1 right to left.

The below code demonstrates the same algo, I have added inline comments for better understanding.

public int longestValidParenthesesWithoutExtraSpace(String s) {
    int left = 0, right = 0, maxlength = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            left++;
        } else {
            right++;
        }
        if (left == right) { // string is valid
            maxlength = Math.max(maxlength, 2 * right);
        } else if (right >= left) { // string becomes invalid
            left = right = 0;
        }
    }

    // Second iteration is to make sure if we had left more from left -> right which when traverse from right -> left
    // can contribute to max length 
    left = right = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == '(') {
            left++;
        } else {
            right++;
        }
        if (left == right) { // string is valid
            maxlength = Math.max(maxlength, 2 * left);
        } else if (left >= right) { // String becomes invalid
            left = right = 0;
        }
    }
    return maxlength;
}

#HappyCoding