32.longest-valid-parentheses.md

32. Longest Valid Parentheses

Dynamic Programming

We'd like to use dp[i] to represent the length of the substring end at i that meets the longest valid parentheses.

We can check if valid only encountering ), so we will perform state transition as encountering ).

TODO: unfinished!!

Stack

TODO: unfinished!!

Brute Force

fun longestValidParentheses(s: String): Int {
    var maxLength = 0
    for (start in 0 until s.length) {
        for (end in start + 2 until s.length step 2) {
            val substring = s.substring(start, end)
            if (isValid(substring)) {
                maxLength = max(maxLength, substring.length)
            }
        }
    }
    return maxLength
}

private fun isValid(s: String): Boolean {
    val stack = Stack<Char>()
    for (c in s) {
        if (c == '(') {
            stack.push(c)
        } else {
            if (stack.isEmpty()) return false
            stack.pop()
        }
    }
    return stack.isEmpty()
}

• Time Complexity: O(n^3).
• Space Complexity: O(n) for stack.

Failed Cases

• "()(()"
• "()(()()"
• "()()(()"
• "()(()())"

Nice Explanation

• https://bangbingsyb.blogspot.com/2014/11/leetcode-longest-valid-parentheses.html
• https://medium.com/@bill800227/leetcode-32-longest-valid-parentheses-ba6a9dff8aa5
• https://dev.twsiyuan.com/2017/12/leetcode-longest-valid-parentheses.html
• https://blog.justin0u0.com/LeetCode-Longest-Valid-Parentheses/
• https://xiaoguan.gitbooks.io/leetcode/content/LeetCode/32-longest-valid-parentheses-hard.html