Swift Leetcode Series : Longest Valid Parentheses
Longest Valid Parentheses (Leetcode 32) -
Difficulty : Hard Link : April Leetcoding Challenge 2021 : Day 3 Given a string containing just the characters '(' and…
If you are unable to view the story you can also read the full story on The Swift Nerd blog with the link above.
Given a string containing just the characters
')', find the length of the longest valid (well-formed) parentheses substring.
Input: s = "(()"
Explanation: The longest valid parentheses substring is "()".Input: s = ")()())"
Explanation: The longest valid parentheses substring is "()()".Input: s = ""
0 <= s.length <= 3 * 104
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.
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.
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 = . 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.
Time = O(N) (Iterating the input elements once)
Space = O(N) (For storing the stack)