October 6Medium

Minimum add to make parentheses valid

String
Stack
Greedy
Bracket Sequences

Problem

A parentheses string is valid if and only if: - It is the empty string, - It can be written as AB (A concatenated with B), where A and B are valid strings, or - It can be written as (A), where A is a valid string.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

• For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".

Return the minimum number of moves required to make s valid.

Solution

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        opened = 0
        ans = 0
        for char in s:
            if char == "(":
                opened += 1
            else:
                if opened:
                    opened -=1 
                else:
                    ans += 1
        return ans + opened