How should I practice Minimum Removal for Balanced Parentheses?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Meta phone screen problems in FastPrep.

Is Minimum Removal for Balanced Parentheses associated with Meta?

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

Problem · String

Minimum Removal for Balanced Parentheses

Learn this problem

● Medium

MetaNEW GRADPHONE SCREEN

See Meta hiring insights

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

makeParenthesesBalanced(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 ).