Swift Leetcode Series : Longest Valid Parentheses

April Leetcoding Challenge 2021: Day 3 (Hard)

Longest Valid Parentheses (Leetcode 32) -

If you are unable to view the story you can also read the full story on The Swift Nerd blog with the link above.

Problem statement

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Examples

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

Constraints

• 0 <= s.length <= 3 * 104
• s[i] is '(', or ')'.

Solution

This is a Leetcode hard problem and it has a lot of possible solutions using stacks, two stacks, dynamic programming and a loop solution. We would be discussion the most intuitive solution which is stack.

Stack approach

If we look carefully, this is an extension of valid parenthesis problem where we would push if ‘(‘ is encountered and pop when we get ‘)’. We need to use the same approach but modify in such a way that we can find the length of the valid parenthesis string. Instead of pushing parenthesis, we can push the indexes on ‘(‘ and whenever we pop() on ‘)’, we can check the top of the stack. The top of the stack will give us the index at which last the time there was no valid parenthesis string found. If we simply subtract it from the current index, we would get the length of that particular valid substring. Since there can be multiple valid substrings in the array, we can use the greedy approach of keeping a max variable and every time we update with the max string length found till that point.

Edge Case

We need to make sure that stack can not be empty at any point. If while popping the stack , the stack is empty, then we will have to insert the current index. Imagine for input = “) ) ( )” , there are multiple closing brackets. If this scenario, till index 1 , stack = [] , index 2 : we push 2 on the stack = [2]. index 3 : when we pop from the stack, since the stack becomes empty there is no way of knowing of the last index from which we could count the string length.

Also, take an example of input = “( )”, if we insert a sentinel value of -1 on the stack. When we would pop() on index 1, the stack would have top of -1 (which we inserted initially). Now length of valid substring = current index — stack.top() => 1 — (-1) = 2 Which is perfect because “()” is a valid substring of length 2.

Code

Complexity

Time = O(N) (Iterating the input elements once)

Space = O(N) (For storing the stack)

Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!

You can find me on TheSwiftNerd | LinkedIn | Github