Minimum Add to Make Parentheses Valid

LeetCode 921, Medium. Topics: String, Stack, Greedy. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 15 parametrized pytest cases, and a playground notebook:

lcpy gen -n 921   # by problem number
lcpy gen -s minimum_add_to_make_parentheses_valid   # by problem name

Problem

A parentheses string is valid if and only if: <ul> <li>It is the empty string,</li> <li>It can be written as <code>AB</code> (<code>A</code> concatenated with <code>B</code>), where <code>A</code> and <code>B</code> are valid strings, or</li> <li>It can be written as <code>(A)</code>, where <code>A</code> is a valid string.</li> </ul> You are given a parentheses string <code>s</code>. In one move, you can insert a parenthesis at any position of the string. <ul> <li>For example, if <code>s = ”()))”</code>, you can insert an opening parenthesis to be <code>”(()))”</code> or a closing parenthesis to be <code>”())))”</code>.</li> </ul> Return the minimum number of moves required to make <code>s</code> valid.

Examples

Input: s = "())"
Output: 1

Input: s = "((("
Output: 3

Constraints

1 <= s.length <= 1000
s[i] is either ’(’ or ’)’.

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(?)
    # Space: O(?)
    def min_add_to_make_valid(self, s: str) -> int:
        open_needed = 0
        insertions = 0
        for char in s:
            if char == "(":
                open_needed += 1
            elif open_needed > 0:
                open_needed -= 1
            else:
                insertions += 1
        return insertions + open_needed

Complexity

Time	Space
O(?)	O(?)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Minimum Add to Make Parentheses Valid

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags