[Leetcode Solution] Longest Valid Parentheses

GOOD PROBLEM

Analysis 

• Very similar to problems like 'Best Time to Buy and Sell Stock' and 'Largest Rectangle in Histogram' which can be easily solved in O(n*n) but has a tricky O(n) solution by two pointers scan or stack.
• As the same of 'Largest Rectangle in Histogram' this problem use a stack to maintain the previous state and calculate the current state in constant time which eventually leads to a O(n) time solution.

Use a stack  to store the previous information. Iterate the input string.

• If string[i] == '(', push it back to the stack and store the position of '('
• If string[i] == ')' then pop the last element in the stack and calculate the length of the substring formed by these ')' and '(' based on the position information stored before.

The tricky is, if a test case exists like this
          "( ) ( )"
the above solution will get two parentheses pairs whose length is 2 for each but cannot sum up them together.

So the solution is adding another pointer 'start' which used to store the start position of a entire valid paired sub string. Because we know that the sub string will become invalid if the number of ')' is larger then '(' when we iterate from left to right. So as long as the number of ')' is not larger then '(', the sub string is still valid and it could be formed as a entire paired sub string.

•  Thus we will only reset the 'start' pointer when stack is empty and the current char is ')'.
• When we calculate the length of sub string, if the stack is empty, we should use the 'start' as the start position rather then the position information stored in the stack.

Note

Code