921.minimum-add-to-make-parentheses-valid.md

921. Minimum Add to Make Parentheses Valid

Stack

We use stack to pair the parentheses. We have to add parentheses to make the parentheses when there is any unmatched left or right parentheses.

fun minAddToMakeValid(s: String): Int {
    if (s.isEmpty()) return 0
    val stack = Stack<Char>()
    var count = 0
    for (c in s) {
        if (c == '(') {
            stack.push(c)
        } else {
            if (stack.isNotEmpty()) {
                stack.pop()
            } else {
                // right is more, we have to add one left parentheses
                count++
            }
        }
    }
    // left is more at the end, we have to add right parentheses
    count += stack.size
    return count
}

• Time Complexity: O(n), where n is the length of the string.
• Space Complexity: O(n).

Greedy

We don't need to use stack to solve this problem. We can use a count variable to store the number of unmatched left parentheses:

• A left parentheses: increase the count. (Count is positive when left > right)
• A right parentheses: decrease the count. (Count is negative when left < right)
• The count is 0 when we have a balanced parentheses.

s = "(()))(("

( ...           count = 1   // Case 1.
(( ...          count = 2
(() ...         count = 1   // Case 2.
(()) ...        count = 0
(())) ...       count = -1  // Case 3.
                count = 0   // Updated to 0
(())( ...       count = 1
(())((          count = 2   // Case 4

There are 4 cases:

• Case 1: We have one left parentheses, and we have string to process, we don't have to add parentheses here, because we can pair it with the right parentheses later.
• Case 2: We have one left and right parentheses, we can pair them.
• Case 3: The count is negative, it indicates that we don't have enough left parentheses to pair with the right parentheses. That's impossible to pair this right parenthesis in future, no matter what the next string is, so we must add 1 to the result now. After adding 1 to the result, we need to reset the count to 0.
• Case 4: We have more unmatched left parentheses and we have no next string to process, we must add the difference to the result now.

贪心策略。我们的每次 add 都是不得不去做的（不 add 就无法成立），所以结果必然是 minimum add.

fun minAddToMakeValid(s: String): Int {
    var minAdd = 0
    var leftCount = 0
    for (c in s) {
        if (c == '(') {
            leftCount++
        } else {
            leftCount--
        }

        // Right > left, it's impossible to match later, we must add one left parentheses.
        if (leftCount < 0) {
            minAdd++
            leftCount = 0 // Now we have a balanced parentheses, reset the count.
            // leftCount++ // Or equivalently, We can also add one left parentheses here.
        }
    }

    // In the end, we have more left parentheses.
    minAdd += leftCount
    return minAdd
}

// Or equivalently, same logic from the stack approach, but without stack.
fun minAddToMakeValid(s: String): Int {
    var leftCount = 0
    var minAdd = 0
    for (c in s) {
        if (c == '(') {
            leftCount++
        } else {
            if (leftCount > 0) {
                leftCount--
            } else {
                minAdd++
            }
        }
    }
    minAdd += leftCount
    return minAdd
}

• Time Complexity: O(n), where n is the length of the string.
• Space Complexity: O(1).

References

• 官神題解 Video