# Longest Valid Parentheses | Leetcode Problem Solution | Hard Problem

*Idea:*

*Idea:*

One of the key things to realize about valid parentheses strings is that they’re entirely self-satisfied, meaning that while you can have one substring that is entirely inside another, you can’t have two substrings that only partially overlap.

This means that we can use a **greedy O(N) time complexity** solution to this problem without the need for any kind of backtracking. In fact, we should be able to use a very standard stack-based valid parentheses string algorithm with just three very minor modifications.

In a standard valid parentheses string algorithm, we iterate through the string (**S**) and push the index (**i**) of any **‘(‘** to our **stack**. Whenever we find a **‘)’**, we match it with the last entry on the **stack** and pop said entry off. We know the string is not valid if we find a **‘)’** while there are no **‘(‘** indexes in the **stack** with which to match it, and also if we have leftover **‘(‘** in the **stack** when we reach the end of **S**.

For this problem, we will need to add in a step that updates our answer (**ans**) when we close a parentheses pair. Since we stored the index of the **‘(‘** in our stack, we can easily find the difference between the **‘)’** at **i** and the last entry in the **stack**, which should be the length of the valid substring which was just closed.

But here we run into a problem because consecutive valid substrings can be grouped into a larger valid substring (ie, **‘()()’ = 4**). So instead of counting from the *last* **stack** entry, we should actually count from the *second to last* entry, to include any other valid closed substrings since the most recent **‘(‘** that will still remain after we pop the just-matched last **stack** entry off.

This, of course, brings us to the second and third changes. Since we’re checking the second to last **stack** entry, what happens in the case of **‘()()’** when you close the second valid substring yet there’s only the one **stack** entry left at the time?

To avoid this issue, we can just wrap the entire string in another imaginary set of parentheses by starting with **stack = [-1]**, indicating that there’s an imaginary **‘(‘** just before the beginning of the string at **i = 0**.

The other issue is that we will want to continue even if the string up to **i** becomes invalid due to a **‘)’** appearing when the **stack** is “empty”, or in this case has only our imaginary index left. In that case, we can just effectively restart our **stack** by updating our imaginary **‘(‘** index (**stack[0] = i**) and continue on.

Then, once we reach the end of **S**, we can just **return ans**.

*Implementation:*

*Implementation:*

There are only minor differences in the code for all four languages.

*Javascript Code:*

The best result for the code below is

76ms / 39.9MB(beats 99% / 78%).

var longestValidParentheses = function(S) { let stack = [-1], ans = 0 for (let i = 0; i < S.length; i++) if (S[i] === '(') stack.push(i) else if (stack.length === 1) stack[0] = i else stack.pop(), ans = Math.max(ans, i - stack[stack.length-1]) return ans};

*Python Code:*

The best result for the code below is

40ms / 14.6MB(beats 88% / 71%).

`class Solution:`

def longestValidParentheses(self, S: str) -> int:

stack, ans = [-1], 0

for i in range(len(S)):

if S[i] == ‘(‘: stack.append(i)

elif len(stack) == 1: stack[0] = i

else:

stack.pop()

ans = max(ans, i — stack[-1])

return ans

*Java Code:*

The best result for the code below is

2ms / 38.7MB(beats 69% / 94%).

`class Solution {`

public int longestValidParentheses(String S) {

Stack<Integer> stack = new Stack<>();

stack.push(-1);

int ans = 0;

for (int i = 0; i < S.length(); i++)

if (S.charAt(i) == ‘(‘) stack.push(i);

else {

stack.pop();

if (stack.isEmpty()) stack.push(i);

else ans = Math.max(ans, i — stack.peek());

}

return ans;

}

}

*C++ Code:*

The best result for the code below is

0ms / 7.1MB(beats 100% / 71%).

class Solution {public: int longestValidParentheses(string S) { vector<int> stack = {-1}; int ans = 0; for (int i = 0; i < S.size(); i++) if (S[i] == '(') stack.push_back(i); else if (stack.size() == 1) stack[0] = i; else { stack.pop_back(); ans = max(ans, i - stack.back()); } return ans; }};

Thank You for reading so far. I am new here. I hope you got what you have come for. Please appreciate it if you liked it. Follow me for more content. Help me with the feedback via commenting the review.