Make The String Great: Stack-Based Pair Removal

LeetCode Make The String Great (Problem 1544) gives you a string of lower and upper case English letters. Your job is to make it "great" by repeatedly removing any adjacent pair where one character is the lowercase version of the other (for example, 'a' next to 'A'). You keep removing until no such pair remains, then return the result.

The problem

You are given a string s containing lowercase and uppercase English letters. A "bad pair" is two adjacent characters where one is the lowercase version of the other, like 'a' and 'A' or 'D' and 'd'. Remove all bad pairs repeatedly until the string has none left. Return the resulting string.

For example, "leEeetcode" contains the bad pair 'e' and 'E' at indices 1 and 2. Removing that pair gives "leetcode", which has no more bad pairs.

The brute force approach

You could scan the string from left to right looking for a bad pair, remove it, then start over from the beginning. Every removal might create a new bad pair (the characters that were previously separated are now adjacent), so you would need to repeat the scan until a full pass finds nothing to remove. In the worst case, you remove one pair per pass and the string has length n, giving O(n^2) time. This works, but there is a much cleaner way.

The key insight

A stack lets you process the entire string in one pass. As you read each character, you compare it against the top of the stack. If they form a bad pair (same letter, different case), you pop the stack. Otherwise, you push the new character. By the time you finish reading the string, the stack contains exactly the characters of the "great" string in order.

This works because removing a bad pair might expose a new bad pair between the character before it and the character after it. The stack naturally handles this: when you pop a character, the next comparison is between the new top of the stack and the next character in the input. There is no need to rescan.

Step-by-step walkthrough

Let's trace through the algorithm on "leEeetcode". We maintain a stack and process each character one at a time. When the current character and the stack's top form a bad pair, we pop instead of pushing.

After processing all nine characters, the stack holds ['l', 'e', 't', 'c', 'o', 'd', 'e'], which we join into "leetcode".

The code

def makeGood(s):
    stack = []
    for ch in s:
        if stack and abs(ord(stack[-1]) - ord(ch)) == 32:
            stack.pop()
        else:
            stack.append(ch)
    return ''.join(stack)

For each character, you check whether the top of the stack and the current character are the same letter with different cases. The ASCII values of a lowercase letter and its uppercase counterpart always differ by exactly 32 (for example, ord('a') = 97 and ord('A') = 65). If the difference is 32, they form a bad pair and you pop. Otherwise, you push the character onto the stack.

Complexity analysis

The stack approach reads each character exactly once and performs at most one push or pop per character. That gives O(n) time. The stack can hold at most n characters in the worst case (when nothing gets removed), so space is O(n).

The building blocks

Stack for adjacent pair matching

The core pattern here is the same one used in removing adjacent duplicates and validating parentheses: use a stack, compare the incoming element against the top, and either pop (match found) or push (no match). The only thing that changes between these problems is the matching condition. For duplicates, you check equality. For parentheses, you check bracket pairing. Here, you check same-letter-different-case.

ASCII case relationship

Every lowercase letter in ASCII is exactly 32 higher than its uppercase counterpart. This means you can toggle case with XOR (ch ^ 32), check for a case mismatch with abs(ord(a) - ord(b)) == 32, or normalize with .lower(). Knowing this relationship is useful across many string problems.

Edge cases

Empty string. If s is empty, the stack stays empty and you return "". The algorithm handles this without special-casing.

Already great. If the string has no bad pairs (like "abc" or "aAbBcC" is not great, but "abcABC" with no adjacent conflicts is), the stack just accumulates every character and you return the original string unchanged.

Entire string cancels out. A string like "aA" or "abBA" cancels completely. In "abBA", reading 'B' pops 'b', then reading 'A' pops 'a', leaving an empty stack. The result is "".

Single character. A string of length 1 can never contain a bad pair. The character just gets pushed and returned.

From understanding to recall

This problem is a close sibling of Remove All Adjacent Duplicates. The only difference is the matching rule: duplicates use equality, and "Make The String Great" uses same-letter-different-case. If you can solve one, you can solve the other by swapping the comparison.

When drilling this problem, focus on the matching condition. The stack pattern itself should feel automatic if you have practiced adjacent duplicate removal or valid parentheses. The part worth internalizing here is the ASCII relationship between upper and lower case letters and how to express the bad pair check concisely.

Also notice that the stack approach processes the entire string in a single left-to-right pass, even though bad pair removal can cascade. The stack naturally handles cascading because popping exposes the previous character for the next comparison. This is the key advantage over the brute force rescan approach.

Related posts

• Valid Parentheses - The classic stack matching problem. Same pattern of comparing the incoming element against the stack top and popping on a match.
• Backspace String Compare - Stack-based string processing where special characters trigger deletions, similar to how bad pairs trigger pops here.
• Remove All Adjacent Duplicates In String - The closest sibling problem. Same stack structure, just a different matching condition (equality instead of case mismatch).