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:
- For left parenthesis, we increase the count.
- 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.
- At the end of iteration, we need to add the right parenthesis for the remaining left parentheses, we add the
count * 2to the result, we need to add two right parentheses for each left parenthesis.
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
}