0032-Longest Valid Parentheses.md

Longest Valid Parentheses

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

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

Solution

O(n):

func longestValidParentheses(_ s: String) -> Int {
        var stack : [Int] = [-1], result = 0
        let input = Array(s)
        for i in 0..<input.count {
            switch (input[i], stack.last) {
                case (")", .some(let last)) where last >= 0 && input[last] == "(":
                stack.removeLast()
                if let peek = stack.last {
                    result = max(result, i-peek)
                }
                default:
                stack.append(i)
            }
        }
        return result
    }