BinarySearch 0178 Minimum Bracket Addition

Problem statement

https://binarysearch.com/problems/Minimum-Bracket-Addition/

Solution

Equal to Leetcode 0921 Minimum Add to Make Parentheses Valid.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        lft = [0]
        for c in s:
            lft += [lft[-1] + (c == "(") - (c == ")")]
            
        rgh = [0]
        for c in s[::-1]:
            rgh += [rgh[-1] + (c == ")") - (c == "(")]
            
        return -min(min(lft), 0) - min(min(rgh), 0)