Greedy counter of owed ')'
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
The code from the episode, ready for LeetCode's Python 3 editor: paste it in and submit.
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.
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