Make The String Great

Make The String Great

What is this problem about?

The Make The String Great problem gives you a string of upper and lower case English letters. A string is considered "bad" if it contains two adjacent characters that are the exact same letter but in different cases (e.g., "aA" or "Bb"). You must make the string "great" by repeatedly removing these adjacent bad pairs until no more exist. Return the resulting string.

Why is this asked in interviews?

This is a fundamental string manipulation and Stack problem. It is highly favored for junior roles because it is identical in logic to classic problems like Valid Parentheses or removing adjacent duplicates. It tests whether a candidate can recognize that when an inner pair is removed, the elements on the outside might crash together to form a new bad pair, requiring a data structure that easily handles backtracking.

Algorithmic pattern used

This problem is perfectly suited for a Stack. You iterate through the characters of the string. For each character, you check if the Stack is not empty and if the current character forms a "bad pair" with the character at the top of the Stack. If it does, you pop the top character off the Stack (destroying the pair). If it doesn't, you push the current character onto the Stack. At the end, the Stack contains the "great" string.

Example explanation

String: "leEeetcode" Initialize Stack: []

• l: Stack ['l']
• e: Stack ['l', 'e']
• E: 'e' and 'E' are the same letter, different cases. Bad pair! Pop 'e'. Stack ['l']
• e: Stack ['l', 'e']
• e: Stack ['l', 'e', 'e']
• t, c, o, d, e all push normally. Resulting string from Stack: "leetcode".

What about "abBA"?

• a: Stack ['a']
• b: Stack ['a', 'b']
• B: Bad pair with 'b'. Pop 'b'. Stack ['a']
• A: Bad pair with 'a'. Pop 'a'. Stack []. Result is "".

Common mistakes candidates make

A major pitfall is using a replace function or standard string concatenation inside a while loop. For example, repeatedly doing s = s.replace("aA", "") for all 26 letters is an $O(N^2)$ operation that is clumsy and inefficient. Another common mistake is checking equality incorrectly. A bad pair exists if abs(char1 - char2) == 32 (the ASCII difference between lower and upper case letters). Simply checking char1.toLowerCase() == char2.toLowerCase() is incomplete because "aa" is NOT a bad pair!

Interview preparation tip

To nail the Make The String Great coding problem, memorize the ASCII difference trick: Math.abs(c1 - c2) == 32. This is the fastest, cleanest way to check if two characters are the same letter but opposite cases. Combined with a Stack (or using a StringBuilder/Array as a stack for optimal performance), you can write a flawless $O(N)$ solution in under 5 minutes.