LeetCode Entry

1541. Minimum Insertions to Balance a Parentheses String

09.10.2026 medium 2026 kotlin rust

Add braces to balance ( with ))

1541. Minimum Insertions to Balance a Parentheses String medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1507

Problem TLDR

Add braces to balance ( with ))

Intuition

Either: track current balance and move the pointer two positions forward; or track needs to be closed count.

Approach

• in the second case we should immediately add to odd to make close brace even if we meet an open brace

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\)

Code

   fun minInsertions(s: String) = run {
        var r = 0
        s.sumOf { if (it == '(') (r % 2).also { r += 2 - it }
                  else if (--r < 0) { r = 1; 1 } else 0 } + r
    }

    pub fn min_insertions(s: String) -> i32 {
        let mut r = 0;
        s.bytes().map(|b| if b < 41 { let m = r % 2; r += 2 - m; m }
        else if r > 0 { r -= 1; 0 } else { r = 1; 1 }).sum::<i32>() + r
    }