Table of Contents

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:2Explanation:The longest valid parentheses substring is "()".

**Example 2:**

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

**Example 3:**

Input:s = ""Output:0

**Constraints:**

`0 <= s.length <= 3 * 10`

^{4}`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 l**eft = 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! 🙂