Make The String Great solution and explanation
Google
9 more videos on this problem
Make The String Great | Google | Easy | Leetcode 1544codestorywithMIK · 12:23 · 18K views
Make The String Great - Leetcode 1544 - PythonNeetCodeIO · 10:53 · 9K views
LeetCode 1544. Make The String Great - Interview Prep Ep 89Fisher Coder · 12:16 · 1K views
1544. Make The String Great (Leetcode Easy)Programming Live with Larry · 2:44 · 950 views
Leetcode | 1544. Make The String Great | Easy | Java SolutionDeveloper Docs · 11:01 · 735 views
1544. Make The String Great |Make The String Great Leetcode Solution| Make The String Great LeetcodeCode With Amit · 10:59 · 563 views
Daily Leetcode #952: Nov 08, 2022 - 1544. Make The String GreatProgramming Live with Larry · 4:19 · 432 views
Make The String Great | LeetCode 1544Competitive Coding · 6:48 · 303 views
LeetCode - 1544. Make The String GreatAditya Mahajan · 7:17 · 292 views
How to Solve "1544 Make The String Great" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 8:48 · 259 views
The problem
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.
def makeGood(s: str) -> str:
stack = []
for c in s:
if stack and (stack[-1] == chr(ord(c) + 32) or stack[-1] == chr(ord(c) - 32)):
stack.pop()
else:
stack.append(c)
return ''.join(stack)
# Example usage
s = "leEeetcode"
print(makeGood(s))public class Solution {
public String makeGood(String s) {
StringBuilder stack = new StringBuilder();
for (char c : s.toCharArray()) {
int len = stack.length();
if (len > 0 && (stack.charAt(len - 1) == c + 32 || stack.charAt(len - 1) == c - 32)) {
stack.deleteCharAt(len - 1);
} else {
stack.append(c);
}
}
return stack.toString();
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "leEeetcode";
System.out.println(solution.makeGood(s));
}
}#include <iostream>
#include <string>
std::string makeGood(const std::string& s) {
std::string stack;
for (char c : s) {
if (!stack.empty() && (stack.back() == c + 32 || stack.back() == c - 32)) {
stack.pop_back();
} else {
stack.push_back(c);
}
}
return stack;
}
int main() {
std::string s = "leEeetcode";
std::string result = makeGood(s);
std::cout << result << std::endl;
return 0;
}function makeGood(s) {
const stack = [];
for (let c of s) {
if (stack.length && (stack[stack.length - 1] === String.fromCharCode(c.charCodeAt(0) + 32) || stack[stack.length - 1] === String.fromCharCode(c.charCodeAt(0) - 32))) {
stack.pop();
} else {
stack.push(c);
}
}
return stack.join('');
}
// Example usage
const s = "leEeetcode";
console.log(makeGood(s));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *makeGood(char *s) {
int n = strlen(s);
char *stack = (char *)malloc((n+1) * sizeof(char));
int sp = 0;
for (int i = 0; i < n; ++i) {
if (sp > 0 && ((stack[sp-1] == s[i] + 32) || (stack[sp-1] == s[i] - 32))) {
sp--;
} else {
stack[sp++] = s[i];
}
}
stack[sp] = '\0';
return stack;
}
int main() {
char s[] = "leEeetcode";
char *result = makeGood(s);
printf("%s\n", result);
free(result);
return 0;
}using System;
using System.Text;
class Solution {
public string MakeGood(string s) {
StringBuilder stack = new StringBuilder();
foreach (char c in s) {
int len = stack.Length;
if (len > 0 && (stack[len - 1] == c + 32 || stack[len - 1] == c - 32)) {
stack.Remove(len - 1, 1);
} else {
stack.Append(c);
}
}
return stack.ToString();
}
static void Main() {
Solution solution = new Solution();
string s = "leEeetcode";
Console.WriteLine(solution.MakeGood(s));
}
}Python uses a list to simulate the stack, where append() adds characters and pop() removes the top when a bad pair is identified. This approach effectively cleans the string in a single iteration.
Time Complexity: O(n) as we iterate through the string once.
Space Complexity: O(n) since up to all characters might be stored temporarily.
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.
def makeGood(s: str) -> str:
chars = list(s)
i = 0
for j in range(len(s)):
if i > 0 and (chars[i - 1] == chr(ord(chars[j]) + 32) or chars[i - 1] == chr(ord(chars[j]) - 32)):
i -= 1
else:
chars[i] = chars[j]
i += 1
return ''.join(chars[:i])
# Example use
s = "leEeetcode"
print(makeGood(s))public class Solution {
public String makeGood(String s) {
char[] chars = s.toCharArray();
int i = 0;
for (int j = 0; j < s.length(); j++) {
if (i > 0 && (chars[i - 1] == chars[j] + 32 || chars[i - 1] == chars[j] - 32)) {
i--;
} else {
chars[i++] = chars[j];
}
}
return new String(chars, 0, i);
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "leEeetcode";
System.out.println(solution.makeGood(s));
}
}#include <iostream>
#include <string>
using namespace std;
string makeGood(string s) {
int i = 0;
for (int j = 0; j < s.length(); j++) {
if (i > 0 && (s[i - 1] == s[j] + 32 || s[i - 1] == s[j] - 32)) {
i--;
} else {
s[i++] = s[j];
}
}
return s.substr(0, i);
}
int main() {
string s = "leEeetcode";
cout << makeGood(s) << endl;
return 0;
}function makeGood(s) {
let chars = s.split('');
let i = 0;
for (let j = 0; j < s.length; j++) {
if (i > 0 && (chars[i - 1] === String.fromCharCode(chars[j].charCodeAt(0) + 32) || chars[i - 1] === String.fromCharCode(chars[j].charCodeAt(0) - 32))) {
i--;
} else {
chars[i++] = chars[j];
}
}
return chars.slice(0, i).join('');
}
// Example usage
const s = "leEeetcode";
console.log(makeGood(s));#include <stdio.h>
#include <string.h>
char* makeGood(char* str) {
int n = strlen(str);
int i, j;
for (i = 0, j = 0; j < n; ++j) {
if (i > 0 && (str[i - 1] == str[j] + 32 || str[i - 1] == str[j] - 32)) {
--i;
} else {
str[i++] = str[j];
}
}
str[i] = '\0';
return str;
}
int main() {
char s[] = "leEeetcode";
char* result = makeGood(s);
printf("%s\n", result);
return 0;
}using System;
public class Solution {
public string MakeGood(string s) {
char[] chars = s.ToCharArray();
int i = 0;
for (int j = 0; j < s.Length; j++) {
if (i > 0 && (chars[i - 1] == chars[j] + 32 || chars[i - 1] == chars[j] - 32)) {
i--;
} else {
chars[i++] = chars[j];
}
}
return new string(chars, 0, i);
}
static void Main() {
Solution solution = new Solution();
string s = "leEeetcode";
Console.WriteLine(solution.MakeGood(s));
}
}Python utilizes in-place manipulation of an allocated list as we drive linear remapping to manage pair validation. This offers unencumbered navigation, quitting extraneous complexity for enduring simplicity.
Time Complexity: O(n) attributed to complete looping.
Space Complexity: O(1) since only input modification occurs without further memory demands.
Approach 3: Default Approach
func makeGood(s string) string {
stk := []rune{}
for _, c := range s {
if len(stk) == 0 || abs(int(stk[len(stk)-1]-c)) != 32 {
stk = append(stk, c)
} else {
stk = stk[:len(stk)-1]
}
}
return string(stk)
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach Using Stack | Time Complexity: O(n) as we iterate through the string once. Space Complexity: O(n) since up to all characters might be stored temporarily. |
| Two Pointer Technique | Time Complexity: O(n) attributed to complete looping. Space Complexity: O(1) since only input modification occurs without further memory demands. |
| Default Approach | – |
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. |
Frequently asked questions
Is Make The String Great easy or hard?
Make The String Great is classified as an Easy problem on LeetCode with an acceptance rate above 68%. The challenge focuses on recognizing the stack pattern and handling character case comparisons efficiently.
Make The String Great Python/Java solution
In Python and Java, the typical solution uses a stack or list to process characters sequentially. Compare the current character with the stack top; if they differ only by case, pop the stack. Otherwise push the character. After processing, join the stack to produce the final string.
How to solve Make The String Great in O(n)?
Scan the string once while maintaining a stack (or simulated stack using a pointer). If the current character and the stack top differ by ASCII value 32, remove the stack top. Otherwise push the character. This single-pass strategy guarantees O(n) time complexity.
What is the best approach for Make The String Great?
The stack-based approach is the most common and intuitive solution. Traverse the string and push characters onto a stack, removing the top when it forms an opposite-case pair with the current character. Each character is processed once, giving O(n) time and O(n) space complexity.
Is Make The String Great asked at Google/Amazon/Meta?
This problem reflects a common interview pattern involving stack-based pair removal and string normalization. Variations of similar problems have appeared in interviews at companies like Amazon and Google when testing string processing and stack fundamentals.
What data structure is used in Make The String Great?
A stack is the primary data structure used to track characters while resolving adjacent opposite-case pairs. The same behavior can also be simulated with a two-pointer technique that treats the result array as a virtual stack.
What is the time complexity of Make The String Great?
The optimal solution runs in O(n) time where n is the length of the string. Each character is pushed to and possibly popped from the stack once. This guarantees linear processing with no nested iteration.