Minimum Remove to Make Valid Parentheses

Remove only unavoidable parentheses

Scan from left to right. Keep a count or stack of indices for unmatched opening parentheses. When seeing (, record it. When seeing ), match it by popping an available opening; if none exists, mark this closing parenthesis for removal because no later character can repair it. After the scan, every opening index left on the stack must also be removed. Build the result while skipping exactly the marked indices, preserving letters and other symbols unchanged.

Why the removals are minimal

An unmatched closing parenthesis is invalid at the instant it appears in every possible prefix, so it must be removed. An opening left unmatched at the end has no later closing partner, so it must also be removed. All other parentheses can remain matched, proving no extra deletions are needed. A boolean removal array or set plus stack uses O(n) space and time. A two-pass counter solution can use O(n) output space with less auxiliary indexing. Test strings with leading closes, trailing opens, nested valid regions, and non-parenthesis characters.