Problem Description

You are given a string s containing both lowercase and uppercase English letters. Your task is to make this string "good" by removing certain pairs of adjacent characters.

A string is considered "good" if it doesn't contain any two adjacent characters where one is a lowercase letter and the other is the same letter in uppercase (or vice versa). For example, 'a' and 'A' are a bad pair, as are 'B' and 'b'.

To make the string good, you need to repeatedly find and remove pairs of adjacent characters that make the string bad. When you remove a pair, the remaining parts of the string join together, potentially creating new adjacent pairs that might also need to be removed.

For example:

• In the string "leEeetcode", the characters 'e' and 'E' at positions 2 and 3 form a bad pair. After removing them, you get "leetcode", which is good.
• In the string "abBAcC", you can remove 'b' and 'B' to get "aAcC", then remove 'a' and 'A' to get "cC", and finally remove 'c' and 'C' to get an empty string "".

The process continues until no more bad pairs exist in the string. An empty string is also considered good.

The solution uses a stack-based approach where each character is compared with the top of the stack. If they form a bad pair (their ASCII values differ by exactly 32, which is the difference between uppercase and lowercase letters), both characters are removed. Otherwise, the current character is added to the stack.

Return the final good string after all possible removals. The answer is guaranteed to be unique for the given constraints.

Intuition

The key insight is recognizing that this problem is similar to matching parentheses or bracket problems. When we remove a bad pair of characters, the characters on either side of them come together and might form a new bad pair. This cascading effect suggests we need to continuously check and remove pairs as we go.

Think about it like a chemical reaction - when two reactive elements (uppercase and lowercase of the same letter) come together, they neutralize each other and disappear. After they disappear, the elements that were previously separated might now be adjacent and could react.

A stack is the perfect data structure for this because:

1. We need to keep track of characters we've seen so far that haven't been "neutralized"
2. We only need to compare with the most recent unmatched character (the top of the stack)
3. When we find a match, we remove both characters instantly

The process works like this: as we traverse the string, we check if the current character forms a bad pair with the last character we kept (top of stack). If they form a bad pair, we remove the last kept character and discard the current one. If not, we keep the current character for future comparisons.

The ASCII value trick (abs(ord(stk[-1]) - ord(c)) != 32) is a clever way to check if two characters are the same letter but different cases. In ASCII, the difference between any lowercase letter and its uppercase counterpart is exactly 32. For example, 'a' is 97 and 'A' is 65, with a difference of 32. This pattern holds for all English letters.

By processing the string in a single pass with a stack, we efficiently handle all the cascading removals without needing to repeatedly scan the string or use recursion.

Learn more about Stack patterns.

Solution Approach

The solution uses a stack-based approach to efficiently process the string in a single pass. Here's how the implementation works:

Data Structure: We use a list stk as a stack to store characters that haven't been neutralized yet.

Algorithm Steps:

1. Initialize an empty stack: stk = [] - This will hold our valid characters as we process the string.

2. Iterate through each character: For each character c in the string s:

3. Check for bad pairs:

   • If the stack is empty (not stk), we have nothing to compare with, so we add the current character
   • If the stack has elements, we check if the top element and current character form a bad pair using: abs(ord(stk[-1]) - ord(c)) != 32

4. Decision Logic:

   • If NOT a bad pair (stack empty OR ASCII difference ≠ 32): Push the current character onto the stack with stk.append(c)
   • If it IS a bad pair (ASCII difference = 32): Remove the top element from the stack with stk.pop() and discard the current character

5. Build the result: After processing all characters, join the remaining characters in the stack to form the final good string: return "".join(stk)

Why the ASCII check works:

• In ASCII, uppercase letters range from 65-90 ('A' to 'Z')
• Lowercase letters range from 97-122 ('a' to 'z')
• The difference between any lowercase and its uppercase is exactly 32
• abs(ord(stk[-1]) - ord(c)) calculates the absolute difference between ASCII values
• If this equals 32, we know they're the same letter in different cases

Time Complexity: O(n) where n is the length of the string - we process each character once

Space Complexity: O(n) in the worst case where no characters form bad pairs, so all characters remain in the stack

Example Walkthrough

Let's trace through the string "abBAcC" step by step:

Initial state: s = "abBAcC", stack = []

Step 1: Process 'a'

• Stack is empty, so add 'a'
• Stack: ['a']

Step 2: Process 'b'

• Top of stack is 'a', check: abs(ord('a') - ord('b')) = abs(97 - 98) = 1 ≠ 32
• Not a bad pair, so add 'b'
• Stack: ['a', 'b']

Step 3: Process 'B'

• Top of stack is 'b', check: abs(ord('b') - ord('B')) = abs(98 - 66) = 32
• This IS a bad pair! Pop 'b' from stack, discard 'B'
• Stack: ['a']

Step 4: Process 'A'

• Top of stack is 'a', check: abs(ord('a') - ord('A')) = abs(97 - 65) = 32
• This IS a bad pair! Pop 'a' from stack, discard 'A'
• Stack: []

Step 5: Process 'c'

• Stack is empty, so add 'c'
• Stack: ['c']

Step 6: Process 'C'

• Top of stack is 'c', check: abs(ord('c') - ord('C')) = abs(99 - 67) = 32
• This IS a bad pair! Pop 'c' from stack, discard 'C'
• Stack: []

Final Result: Join the stack elements: "".join([]) = ""

The string reduces to an empty string after all bad pairs are removed.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input string s.

• The algorithm iterates through each character in the string exactly once using a single for loop.
• For each character, the operations performed are:
  • Checking if the stack is empty: O(1)
  • Computing the ASCII difference using ord(): O(1)
  • Either appending to the stack or popping from the stack: O(1)
• Since we perform constant time operations for each of the n characters, the total time complexity is O(n).

Space Complexity: O(n) where n is the length of the input string s.

• The main space usage comes from the stack stk which stores characters.
• In the worst case, when no characters form "bad pairs" (pairs with ASCII difference of 32, like 'a' and 'A'), all n characters will be pushed onto the stack.
• The final string construction using "".join(stk) creates a new string, but this doesn't increase the asymptotic space complexity as it's still O(n).
• Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Bad Pair Detection Logic

Pitfall: A common mistake is using incorrect conditions to detect bad pairs, such as:

• Checking if characters are simply different cases: stack[-1].lower() == char.lower() and stack[-1] != char
• Using wrong ASCII difference values (e.g., 26 instead of 32)
• Forgetting to use absolute value when calculating ASCII difference

Why it's problematic: These approaches might miss valid pairs or incorrectly identify non-pairs as bad pairs.

Solution: Always use the precise ASCII difference check with absolute value:

abs(ord(stack[-1]) - ord(char)) == 32

2. Modifying String During Iteration

Pitfall: Attempting to modify the original string while iterating through it:

# WRONG - Don't do this!
i = 0
while i < len(s) - 1:
    if abs(ord(s[i]) - ord(s[i+1])) == 32:
        s = s[:i] + s[i+2:]  # Modifying string during iteration
        i = max(0, i-1)  # Trying to backtrack
    else:
        i += 1

Why it's problematic:

• String concatenation creates new strings each time (inefficient)
• Index management becomes complex and error-prone
• Backtracking logic is difficult to implement correctly

Solution: Use a stack-based approach that naturally handles the cascading removals without explicit backtracking.

3. Forgetting Edge Cases

Pitfall: Not handling edge cases properly:

• Empty string input
• Single character string
• String with all same-case letters
• String that becomes empty after all removals

Solution: The stack approach naturally handles all these cases:

# These edge cases are automatically handled:
if s == "":  # Returns ""
if s == "a":  # Returns "a" 
if s == "abc":  # Returns "abc"
if s == "aA":  # Returns ""

4. Using String Concatenation Instead of Stack

Pitfall: Building the result string by concatenation:

# INEFFICIENT approach
result = ""
for char in s:
    if result and abs(ord(result[-1]) - ord(char)) == 32:
        result = result[:-1]  # String slicing creates new string
    else:
        result += char  # String concatenation creates new string

Why it's problematic: Strings are immutable in Python, so each concatenation or slicing operation creates a new string object, leading to O(n²) time complexity.

Solution: Use a list as a stack and join at the end for O(n) complexity:

stack = []
# ... processing logic ...
return "".join(stack)  # Efficient single join operation