LC-0921 Medium LeetCode

921. Minimum Add to Make Parentheses Valid

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 75% Topics: String, Stack, Greedy

Reading material

Strings 12 min Stacks & Queues 11 min Greedy 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def minAddToMakeValid(self, S):
        """
        :type S: str
        :rtype: int
        """
        add, bal, = 0, 0
        for c in S:
            bal += 1 if c == '(' else -1
            if bal == -1:
                add += 1
                bal += 1
        return add + bal

Solution from kamyu104/LeetCode-Solutions · MIT