# Problems

# Pairing

# Monotonic Stack

# LeetCode

# 20. Valid Parentheses

Using a stack

func isValid(s string) bool {
    stack := make([]rune, 0, len(s))
    for _, r := range s {
        if r == '(' || r == '{' || r == '[' {
            stack = append(stack, r)
        } else {
            if len(stack) == 0 {
                return false
            }
            switch stack[len(stack)-1] {
                case '(': 
                if r != ')' {
                    return false
                }
                case '{': 
                if r != '}' {
                    return false
                }
                case '[':
                if r != ']' {
                    return false
                }
            }
            stack = stack[:len(stack)-1]
        }
    }
    if len(stack) > 0 {
        return false
    }
    return trut
}

# 32. Longest Valid Parentheses

leetcode

Only matched parenthesis should count, we could save the indexes of the parenthesis in stack and make a subtraction.
We store every index in the stack. The unpoped indexes are bad indexes. We only need to subtract them using current index to find out the longest contiguous valid parenthesis.

func longestValidParentheses(s string) int {
    stack := make([]int, 0, len(s))
    res := 0
    for i, r := range s {
        if r == '(' {
            stack = append(stack, i)
        } else {
            if len(stack) > 0 && s[stack[len(stack)-1]] == '(' {
                stack = stack[:len(stack)-1]
                if len(stack) > 0 {
                    res = max(res, i - stack[len(stack)-1])
                } else {
          res = i + 1
                }
            } else {
                stack = append(stack, i)
            }
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Previous post: Code - Recursion Next post: Code - String