How should I practice Minimum Remove to Make Valid Parentheses?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Bloomberg LP phone screen and onsite interview problems in FastPrep.

Is Minimum Remove to Make Valid Parentheses associated with Bloomberg LP?

FastPrep tags this as a Bloomberg LP phone screen and onsite interview coding practice problem when the problem catalog has that company and stage context.

Minimum Remove to Make Valid Parentheses

Bloomberg LP● MediumNEW GRADPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

Given a string s containing ASCII letters, digits, opening parentheses, and closing parentheses, remove the minimum possible number of parentheses so that the remaining parentheses are balanced. You may not add or reorder characters.

Use this deterministic rule when several minimum-removal results are possible:

Scan from left to right. Discard every closing parenthesis that has no unmatched opening parenthesis before it.
After that scan, discard the still-unmatched opening parentheses from right to left.

Return the retained characters in their original relative order. Letters and digits are always retained.

Function

minRemoveToMakeValid(s: String) → String

Examples

Example 1

s = "lee(t(c)o)de)"return = "lee(t(c)o)de"

The final closing parenthesis has no matching opening parenthesis, so removing it produces a balanced result with one deletion.

Example 2

s = "a)b(c)d"return = "ab(c)d"

The closing parenthesis after a is unmatched during the left-to-right scan. Every other parenthesis can be retained.

Example 3

s = "))(("return = ""

Both closing parentheses are unmatched, and both opening parentheses remain unmatched, so all four are removed.

Constraints

1 <= s.length <= 100000.
s contains only ASCII letters, digits, (, and ).