Make The String Great - Solution & Explanation
Problem Statement
Given a string s of lower and upper case English letters.
A good string is a string which doesn't have two adjacent characters s[i] and s[i + 1] where:
0 <= i <= s.length - 2s[i]is a lower-case letter ands[i + 1]is the same letter but in upper-case or vice-versa.
To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.
Return the string after making it good. The answer is guaranteed to be unique under the given constraints.
Notice that an empty string is also good.
Example 1:
Input: s = "leEeetcode" Output: "leetcode" Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".
Example 2:
Input: s = "abBAcC" Output: "" Explanation: We have many possible scenarios, and all lead to the same answer. For example: "abBAcC" --> "aAcC" --> "cC" --> "" "abBAcC" --> "abBA" --> "aA" --> ""
Example 3:
Input: s = "s" Output: "s"
Constraints:
1 <= s.length <= 100scontains only lower and upper case English letters.
Approach Overview
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.
Approach 1: Approach Using Stack
This approach involves using a stack data structure to handle the character removals efficiently.
Iterate through each character in the string s. Use the stack to maintain a record of the characters processed so far. For each new character, compare it with the character at the top of the stack. If they form a bad pair (for example, if one is a lower-case and the other is the same letter in upper-case), pop the stack. Otherwise, push the current character onto the stack.
The stack will ensure that all bad pairs are removed as you process the string, and the remaining elements in the stack will form the good string.
In C, we use an array to simulate a stack. We iterate through the string, checking each character against the top of the stack. If a bad pair is found, we decrement the stack pointer, effectively removing the top of the stack. Otherwise, we push the character onto the stack.
Complexity
Time Complexity: O(n), where n is the length of the string. We make a single pass through the string.
Space Complexity: O(n), because we may store all characters of the string in the worst case (if no removals are made).
Approach 2: Two Pointer Technique
The two-pointer technique allows us to traverse the string using two indices to find and remove bad pairs directly. This could potentially minimize contiguous sections of bad pairs before further adjusting the string.
By initially placing one pointer at the start and the other incrementing through the string, check adjacent pairs for bad sequences directly, shifting strings as necessary, allowing further analysis.
While effectively a simulation of stack behavior, avoiding using additional storage structures explicitly, this approach may involve more complex logic to ensure the traversal maintains correct indices.
The two-pointer technique makes dynamics adjustments to remove bad pairs. We use two indices and iteratively validate bad pairs, updating the input directly and correctly retaining the finalized good string.
Complexity
Time Complexity: O(n), iterating through input once.
Space Complexity: O(1) and no auxiliary data structures are used.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach Using Stack | Time Complexity: O(n), where n is the length of the string. We make a single pass through the string. Space Complexity: O(n), because we may store all characters of the string in the worst case (if no removals are made). |
| Two Pointer Technique | Time Complexity: O(n), iterating through input once. Space Complexity: O(1) and no auxiliary data structures are used. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack Simulation | O(n) | O(n) | Most intuitive solution. Best for interviews when modeling pair removals. |
| Two Pointer Technique | O(n) | O(1) | When optimizing memory and performing in-place string transformation. |
Video Solution
Make The String Great | Google | Easy | Leetcode 1544 • codestorywithMIK • 18,495 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Make The String Great easy or hard?
Make The String Great Python/Java solution
How to solve Make The String Great in O(n)?
What is the best approach for Make The String Great?
Is Make The String Great asked at Google/Amazon/Meta?
What data structure is used in Make The String Great?
What is the time complexity of Make The String Great?
Ready to solve this problem?
Practice Make The String Great with our built-in code editor and test cases.
Practice on FleetCode