Today we will try to solve that problem for the Longest valid parentheses. First time I’ve faced the task I did fail, Yes, I’ve thought about the task in right way but had problems in some implementation details. Today, I’ve analysed the problem on the fresh mind and found/fixed my mistakes.

So, task description:

Given a string containing just the characters

`'('`

and`')'`

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

For`"(()"`

, the longest valid parentheses substring is`"()"`

, which has length = 2.

Another example is`")()())"`

, where the longest valid parentheses substring is`"()()"`

, which has length = 4.

**Algorithm analysis:**

Judging to the task description we can image how our algorithm will work. It looks like we started from first element and run to the end when we have open parentheses **“(“** we increment something by one if closed **“)”** – decrement. I clearly see here is LIFO algorithm. OK, we have found data structure which will be used in our algorithm. It will be stack.

OK, now try to analyse some examples from the description.

**()** – easiest case. Just add open element to stack and remove when we have closed one and calculate length.

**(())** – more complex but with the same solution, all will work like for first case.

**()()** – interesting case. We have to save linking between sequence of the open closed parentheses. It means when we calculate length do not clean up current length or start index until -1 rule is happened.

**-1 Rule**. This rule will work in case when we have empty stack and input closed symbol like **()))**. So -1 rule will be triggered on the second closed parentheses.

**(()** – reversed case. In this case we can run in two ways. One is the calculation of length each time when closed parentheses is happened or, run algorithm from right to left like in reverse mode.

OK, let’s implement algorithm.

First implementation is reverse case:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public int longestValidParentheses(String s) { if(s.length() == 0 ) return 0; return Math.max(findLongest(s, 0, s.length()-1, 1, '('), findLongest(s, s.length()-1, -1,-1, ')')); } private int findLongest(String s, int start, int end, int step, char ch) { Stack<String> stack = new Stack<String>(); int longest = 0; int length = 0; String chToAdd = String.valueOf(ch); for(int i = start; i != end; i+=step){ if(s.charAt(i) == ch){ stack.add(chToAdd); }else{ if(!stack.isEmpty()){ stack.pop(); length+=2; if(stack.isEmpty()) longest = Math.max(longest, length); }else{ length = 0; // -1 case } } } return longest; } |

We run from left to right and from right to left and select longest number.

Second one is each time length calculation

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public int longestValidParentheses(String s) { if(s == null || s.length() == 0 ) return 0; Stack<Integer> stack = new Stack<Integer>(); int longest = 0; int last = -1; // -1 case for(int i = 0; i < s.length(); i++){ if(s.charAt(i) == '('){ stack.add(i); }else{ if(stack.isEmpty()){ last = i; }else if(!stack.isEmpty()){ stack.pop(); if(stack.isEmpty()) longest = Math.max(i-last, longest); else longest = Math.max(i-stack.peek(), longest); } } } return longest; } |

Here is we can see each time calculation of the length but we stored into stack position of open parentheses and calculate diff between prev stored position and current position of loop.

That is all, both solutions are accepted by leetcode, but the task is hard and can be faced just in very strong companies.

Cheers.