package daily

import java.util.*

fun main() {
    // 921. 使括号有效的最少添加
    // https://leetcode.cn/problems/minimum-add-to-make-parentheses-valid/
    println(minAddToMakeValid1("()))(("))
}

fun minAddToMakeValid(s: String): Int {
    val stack = Stack<Char>()
    for (c in s) {
        if (c == ')') {
            val peek = if (stack.isEmpty()) {
                null
            }else {
                stack.peek()
            }
            if (peek == '(') {
                stack.pop()
            }else {
                stack.push(c)
            }
        }else {
            stack.push(c)
        }
    }
    return stack.size
}

fun minAddToMakeValid1(s: String): Int {
    // 分别记录左右括号的数量
    var leftCount = 0
    var rightCount = 0
    for (c in s) {
        if (c == '(') {
            // 遇到左括号，直接 leftCount++，不管有没有右括号，
                // 因为即使有右括号，也是在当前左括号之前出现的，不能和当前左括号匹配
            leftCount++
        }else {
            // 遇到右括号
            if (leftCount > 0) {
                // 有左括号可以匹配
                leftCount--
            }else {
                // 没有左括号可以匹配
                rightCount++
            }
        }
    }
    return leftCount+rightCount
}
