Longest Valid Parentheses

Leetcode 32. Longest Valid Parentheses

Problem

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 ')'.

Source : Leetcode 32. Longest Valid Parentheses

Solution

We can calculate number of left brackets and right brackets from the beginning and when left = right, we can take the length of valid parentheses and update our answer.

Consider the test cases :

a. Case-1: ( ( ( ) ) )

In this case when we are at the 3rd left bracket, left = 3 and right = 0. When we reach at the end we get left = 3 and right = 3. So, the max length will be 2 * left or right = 6.

b. Case-2: ( ( ( ) )

In this case, at the end of the string we get left = 3 and right = 2. So, we never get left and right equal. To handle this kind of situation, we can traverse from last of the string as well. If we traverse from last, we will get right = 2 and left = 2 when we are at index = 1. Thus we will get the answer 4 (2 * left or right).

The Algorithm

Initialize left = right = 0.

Start from beginning and count left and right as you go. If at any point left = right, get length and update answer. If at any point right > left, reinitialize left = right = 0.

Re-Initialize left = right = 0.

Start from end and count left and right as you go. If at any point left = right, get length and update answer. If at any point left > right, reinitialize left = right = 0.

C++ Code

class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0;
        int right = 0;
        int ans = 0;
        int len = s.size();
        
        for(int i = 0; i < len; i++){
            if(s[i] == '(')
                left++;
            else
                right++;
            
            if(left == right)
                ans = max(ans, 2 * left);
            else if(right >= left)
                left = right = 0;
        }
        left = right = 0;
        for(int i = len - 1; i >= 0; i--){
            if(s[i] == '(')
                left++;
            else
                right++;
            
            if(left == right)
                ans = max(ans, 2 * left);
            else if(left >= right)
                left = right = 0;
        }
        return ans;
    }
};

Conclusion

If you like this post or hate it, please write your opinion in the comment section. For more posts like this, please check below or go to the home page.

Happy Coding! 🙂