Leetcode Problem 1541. Minimum Insertions to Balance a Parentheses String

1541. Minimum Insertions to Balance a Parentheses String

Leetcode Solutions

[Python/Java] Straight Forward One Pass

  1. Initialize res to 0 (to count insertions) and right to 0 (to count the number of right parentheses needed).
  2. Iterate through each character c in the string s.
    • If c is '(', check if right is odd. If so, decrement right and increment res.
    • Then, increment right by 2, anticipating two ')' for each '('.
    • If c is ')', decrement right.
    • If right is negative after decrementing, increment right by 2 and res by 1.
  3. After the iteration, add right to res to account for any remaining unbalanced parentheses.
  4. Return res as the minimum number of insertions needed.
UML Thumbnail

Simple O(n) stack solution with detailed explanation

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...