Make The String Great - Video Solutions

Problem Overview: You are given a string containing lowercase and uppercase English letters. A string becomes "good" when it does not contain two adjacent characters that represent the same letter but in different cases (for example 'aA' or 'Bb'). The task is to repeatedly remove such pairs until no more invalid pairs exist and return the final string.

The key observation: two characters cancel each other when they represent the same alphabet letter but have different ASCII cases. In ASCII, the difference between lowercase and uppercase versions of the same letter is exactly 32. This allows quick detection while scanning the string.

Approach 1: Stack Simulation (O(n) time, O(n) space)

This approach processes the string from left to right while maintaining a stack of characters that form the current "good" prefix. For each character, compare it with the top element of the stack. If the stack top and the current character represent the same letter with opposite case (absolute ASCII difference of 32), remove the top element instead of pushing the new one. Otherwise, push the character onto the stack.

This works because any invalid pair must appear as adjacent characters after previous removals. The stack naturally maintains the latest valid prefix and handles cascading removals efficiently. Each character is pushed and popped at most once, giving O(n) time complexity and O(n) auxiliary space.

This solution relies on a classic stack pattern frequently used in problems involving pair cancellation or bracket matching. The input itself is treated as a sequence of characters, making it a straightforward string processing task.

Approach 2: Two Pointer Technique (O(n) time, O(1) extra space)

The stack behavior can be simulated using two pointers on a character array. Convert the string to a mutable array and maintain a pointer write that represents the top of a virtual stack. Iterate through the string using another pointer read. For each character, check whether the previous character in the result (at write - 1) forms a bad pair with the current character.

If they cancel out, simply decrement write to remove the previous character. Otherwise, place the current character at index write and increment the pointer. This effectively builds the result in-place while maintaining the same behavior as a stack.

The algorithm still processes each character once, giving O(n) time complexity. Because the stack is simulated inside the same array, the extra space drops to O(1) excluding the output. This pattern is closely related to the two pointers technique used for in-place array transformations.

Recommended for interviews: Interviewers typically expect the stack-based solution because it directly models the pair-removal behavior and is easy to reason about. Implementing it with a real stack demonstrates clear understanding of the cancellation pattern. The two-pointer optimization shows deeper familiarity with in-place techniques and space optimization, which can be a strong follow-up improvement once the stack solution is established.