IRAMIACADEMY Picture it. Then code it.
Problem 1541Medium

Minimum Insertions to Balance a Parentheses String

String · Stack · Greedy · Bracket Sequences

Greedy counter of owed ')'

solution.py
class Solution:
    def minInsertions(self, s):
        owed = 0  # ')' characters still needed to close the open '('
        insertions = 0
        for ch in s:
            if ch == "(":
                if owed % 2 == 1:
                    # previous '(' only got one ')' before this '(': add the missing one
                    insertions += 1
                    owed -= 1
                owed += 2
            else:
                owed -= 1
                if owed == -1:
                    # ')' with no opener: insert a '(' (which now owes one more ')')
                    insertions += 1
                    owed = 1
        return insertions + owed
Time O(n)Space O(1)

The code from the episode, ready for LeetCode's Python 3 editor: paste it in and submit.

The idea

A closing parenthesis here costs two, so we turn the whole string into a running IOU: every opener owes two coins, and one counter settles the debt in a single pass.

Check our socials
Another way: Stack of open parentheses
solution.py
class Solution:
    def minInsertions(self, s):
        stack = []
        insertions = 0
        i = 0
        while i < len(s):
            if s[i] == "(":
                stack.append("(")
                i += 1
                continue
            # s[i] is ')': a closer needs two in a row
            if i + 1 < len(s) and s[i + 1] == ")":
                i += 2  # already a full "))"
            else:
                insertions += 1  # lone ')' -> insert one more ')'
                i += 1
            # the "))" needs an opener before it
            if stack:
                stack.pop()
            else:
                insertions += 1  # insert a '(' in front
        # every unmatched '(' still needs "))"
        insertions += 2 * len(stack)
        return insertions
Time O(n)Space O(n)