LC 1541 [M] Minimum Insertions to Balance a Parentheses String - ALawliet/algorithms GitHub Wiki
class Solution:
def minInsertions(self, s):
res = 0 # num already added
right = 0 # num right needed for this pair
for c in s:
if c == '(':
if right % 2: # is odd )
res += 1 # by adding 1 () -> ())
right -= 1 # we no longer need a right for this pair
right += 2 # now we need new pair )) again
elif c == ')':
right -= 1 # we closed this right ) -> .
if right < 0: # if we from 0 to -1
res += 1 # we need to add ( before it for this pair
right += 2 # now we need new pair )) again
return res + right
replace trick
class Solution:
def minInsertions(self, s: str) -> int:
s = s.replace('))', '}')
added = 0
l = 0
for c in s:
if c == '(':
l += 1
else:
# For ) you need to add 1 char to get ))
if c == ')':
added += 1
# Matching ( for ) or ))
if l:
l -= 1
# No Matching ( for ) or ))
# Need to insert ( to balance string
else:
added += 1
return added + (2 * l) # added + )) for every (