Practice/Meta/Leetcode 301. Remove Invalid Parentheses

Leetcode 301. Remove Invalid Parentheses

CodingMust

Problem

You are given a string containing lowercase letters, opening parentheses (, and closing parentheses ). Some of the parentheses may be misplaced or unmatched, making the string invalid.

Your task is to remove the minimum number of parentheses (opening or closing) to make the string valid, and return all possible distinct valid strings that can be formed this way.

A valid string is one where:

• Every opening parenthesis has a matching closing parenthesis
• Every closing parenthesis has a matching opening parenthesis that comes before it
• Letters can appear anywhere and are always kept

Requirements

1. Remove the minimum number of parentheses to make the string valid
2. Return all distinct valid strings possible with minimum removals
3. Letters in the string must be preserved in their original positions
4. The order of characters (including remaining parentheses) must be maintained
5. If multiple valid strings exist with the same minimum number of removals, return all of them

Constraints

• 1 ≤ length of s ≤ 25
• s consists of lowercase English letters and parentheses ( and )
• Time complexity should be reasonable for the input size
• Results should contain no duplicates

Examples

Example 1:

Input: s = "()())()" Output: ["(())()", "()()()"] Explanation: We need to remove exactly 1 closing parenthesis. Removing the one at index 4 gives "(())()", and removing the one at index 2 gives "()()()".

Example 2:

Input: s = "(a(b(c)d" Output: ["a(b(c)d)", "(ab(c)d)", "(a(bc)d)", "(a(b)cd)"] Explanation: We need to remove 2 opening parentheses. Different removal combinations give 4 distinct valid strings.

Example 3:

Input: s = "(a)(b)" Output: ["(a)(b)"] Explanation: The string is already valid, so no removals are needed.

Example 4:

Input: s = "(((" Output: [""] Explanation: All parentheses must be removed since none can be matched.