LeetCode-in-All
32. Longest Valid Parentheses
Hard
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”.
Example 2:
Input: s = “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”.
Example 3:
Input: s = “”
Output: 0
Constraints:
0 <= s.length <= 3 * 104s[i]is'(', or')'.
Solution
defmodule Solution do
@spec longest_valid_parentheses(s :: String.t()) :: integer
def longest_valid_parentheses(s) do
s
|> String.graphemes()
|> dp([], 0)
end
def dp([], _, result), do: result
def dp(["(" | tail], queue, result) do
dp(tail, [0 | queue], result)
end
def dp([")" | tail], queue, result) do
{new_queue, new_result} = pop_until(queue, [])
dp(tail, new_queue, max(result, new_result))
end
def pop_until([], _), do: {[], 0}
def pop_until([0 | tail], rest) do
n = List.first(tail)
n = if n, do: n, else: 0
tail = if n > 0, do: tl(tail), else: tail
result = Enum.sum(rest) + n + 2
{[result | tail], result}
end
def pop_until([h | tail], rest) do
pop_until(tail, [h | rest])
end
end