Leetcode 1648 Solution

This article provides solution to leetcode question 1648 (minimum-insertions-to-balance-a-parentheses-string)
Categories:
Tags:
Access this page by simply typing in "lcs 1648" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string

Solution

class Solution:
    def minInsertions(self, s: str) -> int:
        ans = 0
        lvl = 0
        for ch in s:
            if ch == '(':
                if lvl == -1:
                    ans += 2
                    lvl = 0
                elif lvl % 2 == 1:
                    ans += 1
                    lvl -= 1
                lvl += 2
            else:
                lvl -= 1

                if lvl == -2:
                    ans += 1
                    lvl += 2

        if lvl == -1:
            ans += 2
        elif lvl > 0:
            ans += lvl

        return ans