Make the String Great — Stack Adjacent Pair Removal

Problem Statement#

Given a string s of lower and upper case English letters, a "good" string has no two adjacent characters s[i] and s[i + 1] where s[i] is a lowercase letter and s[i + 1] is the same letter in uppercase, or vice versa.

To make a string good, choose two adjacent characters that make it bad and remove them. Repeat until the string is good. Return the resulting good string. It is guaranteed the answer is unique.

Constraints:

• 1 <= s.length <= 100
• s contains only lower and upper case English letters.

Input:  s = "leEeetcode"
Output: "leetcode"
Explanation: Remove 'eE' → "leetcode". No more bad pairs.

Input:  s = "abBAcC"
Output: ""
Explanation: Remove 'bB' → "aAcC", remove 'aA' → "cC", remove 'cC' → "".

Input:  s = "s"
Output: "s"
Explanation: Single character — already good.

Why This Problem Matters#

LC 1544 is a direct application of the stack-based adjacent pair elimination pattern — the same core technique used in Remove All Adjacent Duplicates in String (LC 1047), Remove K Digits (LC 402), and Zuma Game (LC 488). Mastering this pattern on a simple problem like Make the String Great prepares you for the harder monotonic stack variants asked at FAANG.

The key insight this problem teaches: when you process a character and it "cancels" with the stack top, a new pair may form at the top after the pop. This cascading cancellation effect means you cannot process removals in isolation — you must use a stack to handle chains of cancellations naturally.

The problem appears in Amazon and Google phone screens as a warm-up for string manipulation and stack reasoning.

The Core Insight#

The naive approach — scan for bad pairs, remove them, and repeat — could take O(n^2) time in the worst case (consider aAbBcC...: each pass removes one pair, requiring n/2 passes of O(n) work each).

Stack approach (O(n)): Process each character left to right. For each character c:

• If the stack top exists and is the same letter as c but different case, they form a bad pair — pop the stack (they cancel).
• Otherwise, push c onto the stack.

Why does this work? When a bad pair is found and removed, we check whether the new stack top forms a bad pair with the next character automatically — because the next character immediately comes in and compares with the new top. The stack naturally handles cascading cancellations without extra passes.

Checking "same letter, different case": Two characters form a bad pair if and only if c.lower() == top.lower() and c != top. Equivalently, abs(ord(c) - ord(top)) == 32 (the ASCII difference between lowercase and uppercase of the same letter is 32).

Visual Dry Run#

Input: s = "abBAcC"

Stack is empty → result is "".

Notice step 4: after removing 'bB', 'A' now faces 'a' on the stack — a cascading cancellation handled automatically by the stack.

Input: s = "leEeetcode"

Result: "leetcode".

Solution (Optimal)#

# Python — stack-based adjacent pair removal, O(n) time and space
def makeGood(s: str) -> str:
    stack = []
 
    for c in s:
        # Check if current char forms a bad pair with the stack top
        # Same letter (case-insensitive) but different case means different char value
        if stack and stack[-1] != c and stack[-1].lower() == c.lower():
            stack.pop()   # remove the bad pair
        else:
            stack.append(c)  # push surviving character
 
    return ''.join(stack)

// JavaScript — stack-based adjacent pair removal, O(n) time and space
function makeGood(s) {
    const stack = [];
 
    for (const c of s) {
        const top = stack[stack.length - 1];
        // Bad pair: same letter, different case (one upper, one lower)
        if (stack.length > 0 && top !== c && top.toLowerCase() === c.toLowerCase()) {
            stack.pop();
        } else {
            stack.push(c);
        }
    }
 
    return stack.join('');
}

Complexity:

Common Mistakes#

1. Using ord(c) - ord(top) == 32 without handling both orderings. The uppercase letter has a lower ASCII value than its lowercase counterpart. 'A' is 65, 'a' is 97. The difference is 32, but which direction? Check abs(ord(c) - ord(top)) == 32 to handle both orderings correctly.

2. Not checking stack[-1] != c. Two identical characters (e.g., 'a' and 'a') have the same lowercase but are not a bad pair. The condition requires that they differ (one is uppercase, one is lowercase). Without != c, you would pop on 'a'+'a' pairs incorrectly.

3. Using a list and joining at each step. Only join once at the end: ''.join(stack). Joining inside the loop is O(n^2) overall.

4. In Java, building the result incorrectly. Java's ArrayDeque as a stack iterates in LIFO order. When building the result string, pop all elements and reverse, or iterate from bottom to top using an ArrayList or by converting the deque to an array.

5. Forgetting empty string input. If s = "", the loop never executes and the result is "" — the stack is empty and ''.join([]) returns "". Handle this gracefully by not special-casing it (the loop handles it automatically).

Interview Tips#

• Identify the cascading pattern: "When a pair is removed, the characters on either side may now form a new bad pair. A stack handles this automatically — after popping, the next character is compared with the new stack top."
• Compare with the naive approach: "The naive O(n^2) approach re-scans from the beginning after each removal. The stack avoids re-scanning by keeping the processed prefix in sorted order."
• Mention the ASCII trick as a cleaner alternative: abs(ord(c) - ord(top)) == 32 — but clarify that top.lower() == c.lower() and top != c is more readable.

Follow-up Questions#

1. Remove All Adjacent Duplicates (LC 1047) — same pattern but without the case distinction: pop if top equals current character.
2. Remove All Adjacent Duplicates II (LC 1209) — pop if top equals current and the count reaches k; use a stack of (char, count) pairs.
3. Minimum steps to make string good. The number of pops is the answer — count how many pairs are removed during the stack pass.
4. What if "bad pair" means same letter same case? That is the adjacent duplicates removal problem — swap the condition.
5. Can you do it without a stack? Two-pointer approach: one pointer writes surviving characters in-place, the other reads — similar to the approach for in-place string compression.

Key Takeaways#

• The stack adjacent-pair-removal pattern: push each character; if it forms a bad pair with the stack top, pop instead of pushing. This handles cascading cancellations in a single O(n) pass.
• Bad pair condition: same letter, different case — top.lower() == c.lower() and top != c, or equivalently abs(ord(top) - ord(c)) == 32.
• A stack is necessary because removing one pair can expose a new pair — the stack naturally "re-checks" the new top with the next incoming character.
• The naive O(n^2) approach re-scans after every removal; the stack reduces this to O(n) by processing each character exactly once.
• This pattern is the foundation for Remove All Adjacent Duplicates (LC 1047), Remove K Digits (LC 402), and the harder monotonic stack problems in FAANG interviews.
• Always join the stack into a string at the end — not character by character — to maintain O(n) overall time.