Minimum Remove to Make Valid Parentheses

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

lcpy gen -n 1249   # by problem number
lcpy gen -s minimum_remove_to_make_valid_parentheses   # by problem name

Problem

Given a string s of '(' , ')' and lowercase English characters. Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string. Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
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.

Examples

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Input: s = "a)b(c)d"
Output: "ab(c)d"

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Constraints

1 <= s.length <= 10^5
s[i] is either '(' , ')', or lowercase English letter.

Solution

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

class Solution:
    # Time: O(len(s))
    # Space: O(len(s))
    def min_remove_to_make_valid(self, s: str) -> str:
        chars = list(s)
        stack: list[int] = []
        for i, char in enumerate(chars):
            if char == "(":
                stack.append(i)
            elif char == ")":
                if stack:
                    stack.pop()
                else:
                    chars[i] = ""
        for i in stack:
            chars[i] = ""
        return "".join(chars)

Complexity

Time	Space
O(len(s))	O(len(s))

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Minimum Remove to Make Valid Parentheses

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags