108. Valid Parentheses II - Remove Invalid Parentheses

You're building a code formatter that needs to fix invalid parentheses in user input. Instead of just validating, you need to remove the minimum number of invalid parentheses to make the string valid.

Given a string s containing only the characters '(', ')', and lowercase letters, remove the minimum number of invalid parentheses to make the input string valid.

Return all possible results in any order.

A string is valid if:

1. Every opening parenthesis has a matching closing parenthesis
2. Parentheses are closed in the correct order
3. No unmatched parentheses remain

Requirements

1. Basic Functionality

• Remove minimum invalid parentheses
• Return all valid results
• Handle strings with letters and parentheses
• Preserve order of remaining characters

Example Usage

removeInvalidParentheses("()())()");
// ["()()()", "(())()"]
// Removed one ')' from position 3 or 4

removeInvalidParentheses("(a)())()");
// ["(a)()()", "(a())()"]
// Removed one ')' to make valid

removeInvalidParentheses(")(");
// [""]
// Both parentheses are invalid, remove both

Real-World Context

This problem models real code formatting features:

• Code formatters: Fix invalid parentheses in code
• Text editors: Auto-correct parentheses errors
• Parsers: Clean input before parsing
• Linters: Suggest fixes for syntax errors