January 31, 2021

Hello fellow devs π! Today we have a hard LeetCode problem to solve (Itβs not that hard by the way π).

Given a string containing just the characters `(`

and `)`

, find the length of the longest valid (well-formed) parentheses substring.

- 0 β€
`s.length`

β€ 3 Γ 10^{4} `s[i]`

is`(`

, or`)`

.

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
```

The problem is very straight forward. We will be given a string containing only two symbols β `(`

and `)`

. We need to find the length of the longest valid substring. A valid substring is a substring which has an equal number of left parentheses `(`

and right parentheses `)`

.

The naive approach is creating all the possible substrings and then choose the longest substring among the valid substrings. A valid substring can be found using the approach discussed in the post β LeetCode #20 β Valid Parentheses. But this approach takes ** O(n^{2})** time which is not acceptable.

Can we do better π€? The important thing here is we only have to find the **length** of the valid substring. What if we keep track of counts of left parenthesis `(`

and right parenthesis `)`

? As long as the counts of both are same, we can conclude that they form a valid substring. We can thus take the longest such substring.

The algorithm is simple β

- Loop through the string from left to right and store the counts of both type of parentheses in two variables
`left`

and`right`

. - If
`left == right`

, it means we have valid substring. - We can then find if the length of current valid substring (
`left + right`

) is the maximum or not. - If
`right > left`

, it means we have invalid string, and we will reset`left`

and`right`

to zero. - Repeat the steps 1-4 looping string from right to left and reset the counters as soon as
`left > right`

.

Since we are looping the string twice, the time complexity will be ** O(n)**.

We are not using any data structures to store intermediate computations, hence the space complexity will be ** O(1)**.

```
public class LongestValidParentheses {
public int longestValidParentheses(String s) {
// Variable to store the longest valid parentheses
int count = 0;
// Left counter will count the number of '('
int left = 0;
// Right counter will count the number of ')'
int right = 0;
// Loop through the string from left to right.
// This will take care of extra right parentheses
for (int i = 0; i < s.length(); i++) {
// Current character
char c = s.charAt(i);
if (c == '(') {
left++;
}
if (c == ')') {
right++;
}
// If both left and right are equal,
// it means we have a valid substring
if (left == right) {
count = Math.max(count, left + right);
}
// If right is greater than left,
// it means we need to set both
// counters to zero
if (right > left) {
left = right = 0;
}
}
// Reset left and right
left = right = 0;
// Follow the same approach but now loop the string
// from right to left. This will take care of extra
// left parentheses
for (int i = s.length() - 1; i >= 0; i--) {
// Current character
char c = s.charAt(i);
if (c == '(') {
left++;
}
if (c == ')') {
right++;
}
// If both left and right are equal,
// it means we have a valid substring
if (left == right) {
count = Math.max(count, left + right);
}
// If right is greater than left,
// it means we need to set both
// counters to zero
if (left > right) {
left = right = 0;
}
}
return count;
}
}
```

```
def longestValidParentheses(s: str) -> int:
# Variable to store the longest valid parentheses
count = 0
# Left counter will count the number of '('
left = 0
# Right counter will count the number of ')'
right = 0
# Loop through the string from left to right.
# This will take care of extra right parentheses
for i in range(len(s)):
# Current character
c = s[i]
if c == '(':
left += 1
if c == ')':
right += 1
# If both left and right are equal,
# it means we have a valid substring
if left == right:
count = max(count, left + right)
# If right is greater than left,
# it means we need to set both
# counters to zero
if right > left:
left = right = 0
# Reset left and right
left = right = 0
# Follow the same approach but now loop the string
# from right to left. This will take care of extra
# left parentheses
for i in range(len(s) - 1, -1, -1):
# Current character
c = s[i]
if c == '(':
left += 1
if c == ')':
right += 1
# If both left and right are equal,
# it means we have a valid substring
if left == right:
count = max(count, left + right)
# If right is greater than left,
# it means we need to set both
# counters to zero
if left > right:
left = right = 0
return count
```

```
var longestValidParentheses = function (s) {
// Variable to store the longest valid parentheses
let count = 0;
// Left counter will count the number of '('
let left = 0;
// Right counter will count the number of ')'
let right = 0;
// Loop through the string from left to right.
// This will take care of extra right parentheses
for (let i = 0; i < s.length; i++) {
// Current character
let c = s[i];
if (c === '(') {
left++;
}
if (c === ')') {
right++;
}
// If both left and right are equal,
// it means we have a valid substring
if (left === right) {
count = Math.max(count, left + right);
}
// If right is greater than left,
// it means we need to set both
// counters to zero
if (right > left) {
left = right = 0;
}
}
// Reset left and right
left = right = 0;
// Follow the same approach but now loop the string
// from right to left. This will take care of extra
// left parentheses
for (let i = s.length - 1; i >= 0; i--) {
// Current character
let c = s[i];
if (c === '(') {
left++;
}
if (c === ')') {
right++;
}
// If both left and right are equal,
// it means we have a valid substring
if (left === right) {
count = Math.max(count, left + right);
}
// If right is greater than left,
// it means we need to set both
// counters to zero
if (left > right) {
left = right = 0;
}
}
return count;
};
```

```
fun longestValidParentheses(s: String): Int {
// Variable to store the longest valid parentheses
var count = 0
// Left counter will count the number of '('
var left = 0
// Right counter will count the number of ')'
var right = 0
// Loop through the string from left to right.
// This will take care of extra right parentheses
for (element in s) {
// Current character
if (element == '(') {
left++
}
if (element == ')') {
right++
}
// If both left and right are equal,
// it means we have a valid substring
if (left == right) {
count = count.coerceAtLeast(left + right)
}
// If right is greater than left,
// it means we need to set both
// counters to zero
if (right > left) {
right = 0
left = right
}
}
// Reset left and right
right = 0
left = right
// Follow the same approach but now loop the string
// from right to left. This will take care of extra
// left parentheses
for (i in s.length - 1 downTo 0) {
// Current character
val c = s[i]
if (c == '(') {
left++
}
if (c == ')') {
right++
}
// If both left and right are equal,
// it means we have a valid substring
if (left == right) {
count = count.coerceAtLeast(left + right)
}
// If right is greater than left,
// it means we need to set both
// counters to zero
if (left > right) {
right = 0
left = right
}
}
return count
}
```

Congratulations π! Today we solved another **hard** LeetCode problem to determine the length of the longest valid parentheses.

I hope you enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork πͺ and star β it.

Till next timeβ¦ Happy coding π and Namaste π!