Practice/Google/Remove Bad Pairs from a String

Remove Bad Pairs from a String

CodingMust

Problem

Given a string containing uppercase and lowercase English letters, repeatedly remove adjacent pairs of characters where both characters are the same letter but in opposite cases (one uppercase, one lowercase). Continue this process until no more such pairs can be removed.

For example, the pair "aA" should be removed, as should "Aa", "bB", "Bb", etc. After removing a pair, the remaining characters are concatenated, which may create new adjacent pairs that also need to be removed.

Return the final string after all possible eliminations.

Requirements

1. Process the string to find adjacent characters that form opposite-case pairs
2. Remove these pairs continuously until no more exist
3. The order of remaining characters must be preserved
4. Handle cascading eliminations where removal of one pair creates a new adjacent pair

Constraints

• 0 ≤ length of string ≤ 10,000
• String contains only English letters (a-z, A-Z)
• Time complexity should be O(n) where n is the length of the string
• Space complexity should be O(n)

Examples

Example 1:

Input: s = "aAbB" Output: "" Explanation: Remove "aA" → "bB", then remove "bB" → ""

Example 2:

Input: s = "abBA" Output: "aa" Explanation: Remove "bB" → "aBA", then remove "BA" → "aa"

Example 3:

Input: s = "leEeetcode" Output: "leetcode" Explanation: Remove "eE" → "leEtcode", then remove "eE" → "letcode", no more pairs to remove but wait - actually "letcode" has no bad pairs, but let me recalculate: "leEeetcode" → remove "Ee" → "leEtcode" → remove "eE" → "letcode". Actually reviewing: "leEeetcode" - first "Ee" at positions 2,3 → "leEtcode" → "eE" at positions 2,3 → "letcode"

Example 4:

Input: s = "aBbAcCdD" Output: "" Explanation: Multiple cascading eliminations eventually remove all characters