Longest Valid Parentheses (Leetcode 32)

Difficulty : Hard Link :April Leetcoding Challenge 2021 : Day 3

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.

var maxLength = 0
for i in 0..<input.count {
if input[i] == "(" {
// push index on the stack
}
else{
// pop
// Update max length ( maxLength found till now , current valid substring length , ie current index – stack.top)
maxLength = max(maxLength, i stack.top())
}
}
view raw maxLength.Swift hosted with ❤ by GitHub

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

class Solution {
func longestValidParentheses(_ s: String) -> Int {
var maxLength = 0
var stack = [Int]()
stack.append(-1)
for (index,elem) in s.enumerated(){
if elem == "(" {
stack.append(index)
}
else {
stack.popLast()
if let last = stack.last {
maxLength = max(maxLength, index last)
}
else{
stack.append(index)
}
}
}
return maxLength
}
}

Complexity

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *