Skip to content

1541.minimum-insertions-to-balance-a-parentheses-string.md

Latest commit

 

History

History
81 lines (73 loc) · 3.73 KB

1541.minimum-insertions-to-balance-a-parentheses-string.md

File metadata and controls

81 lines (73 loc) · 3.73 KB

1541. Minimum Insertions to Balance a Parentheses String

Stack (Greedy Counting)

It's a variant of 921. Minimum Add to Make Parentheses Valid. The difference is that we need to match one left parenthesis ( with two right parentheses )). We can use the similar approach from it:

  1. For left parenthesis, we increase the count.
  2. For right parenthesis, we check if we have two adjacent right parentheses:
    • There are two right parentheses, we can match one left parenthesis with two right parentheses, we decrease the count.
    • There is only one right parenthesis, we need to add one right parenthesis, and decrease the count because we can match after adding one right parenthesis.
  3. At the end of iteration, we need to add the right parenthesis for the remaining left parentheses, we add the count * 2 to the result, we need to add two right parentheses for each left parenthesis.
  • 遇到左括號：left++
  • 遇到右括號：先檢查右括號有沒有兩個，沒有先補齊右括號。
    • 再來檢查有沒有足夠左括號，沒有再補齊。
    • 記得補齊後就平衡了，所以要把 left = 0 重置。
fun minInsertions(s: String): Int {
    var leftCount = 0
    var insertions = 0
    var i = 0
    while (i < s.length) {
        val c = s[i]
        if (c == '(') {
            leftCount++
        } else {
            // We check if we have two adjacent right parentheses
            if (i + 1 < s.length && s[i + 1] == ')') {
                leftCount-- // We can match one left parenthesis with two right parentheses
                i++ // We have checked i, and i + 1, so we need to skip i + 1
            } else { // We only have one right parenthesis
                insertions++ // We need to add one left parenthesis
                leftCount-- // We match after adding one left parenthesis
            }
        }

        // We check if right parenthesis is more than left parenthesis
        if (leftCount < 0) {
            insertions++ // We need to add one left parenthesis
            leftCount = 0 // We match after adding one left parenthesis
        }
        i++
    }
    return insertions + leftCount * 2 // We need to add two right parentheses for each left parenthesis
}

Or we can count the needed right parentheses directly:

fun minInsertions(s: String): Int {
    var rightNeeded = 0 // How many right parentheses we need to match
    var insertions = 0
    for (c in s) {
        if (c == '(') {
            rightNeeded += 2

            // For the balanced parentheses, we always need the even number of 
            // right parentheses. For odd number, we have to add one right parenthesis.
            if (rightNeeded % 2 != 0) {
                insertions++
                // Because we add one right parenthesis, so the needed right parentheses - 1
                rightNeeded-- 
            }
        } else {
            // We have one right parenthesis, so we decrease the needed right parentheses
            rightNeeded--

            // For negative number of right parentheses, which means left > right
            // We need to add one left parenthesis to match
            if (rightNeeded < 0) {
                insertions++
                rightNeeded += 2 // After adding one left, we need to add two right parentheses to match.
            }
        }
    }
    return insertions + rightNeeded
}

References