Make The String Great — Solution in Python, Java & C++
Make The String Great solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Make The String Great is an easy coding problem on strings and stack, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Strings, Stack
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A string is good if it contains no two adjacent characters s[i] and s[i+1] where one is the lowercase and the other the uppercase form of the same letter.
Repeatedly delete such a pair until the string is good, and return the result. The answer is unique regardless of the order of deletions.
Example 1
Input: s = "leEeetcode"
Output: leetcode
Explanation: Deleting "eE" leaves "leetcode".
Example 2
Input: s = "abBAcC"
Output:
Explanation: Everything cancels out.
Example 3
Input: s = "s"
Output: s
Constraints
1 <= s.length <= 40s consists of upper and lowercase English letters.
Hints for Make The String Great
Hint 1
Push characters onto a stack one at a time.
Hint 2
Before pushing, check whether the character cancels the current top — same letter, different case.
Hint 3
Cancelling can expose a new pair underneath, which the stack handles automatically.
How to solve Make The String Great
Push characters onto a stack, cancelling when the incoming character is the same letter as the top in the opposite case.
Approach
- For each
ch: if the stack top differs fromchbut matches it case-insensitively, pop; otherwise push. - Join the stack.
Why it works
Deleting a bad pair can expose a new bad pair around it, which the stack handles automatically since the top is always the most recent surviving character. The final string is unique, so any deletion order works.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
stack[-1] != chis needed soaais not treated as a bad pair.
Reference solution
Python
def makeGood(s: str) -> str:
stack = []
for ch in s:
if stack and stack[-1] != ch and stack[-1].lower() == ch.lower():
stack.pop()
else:
stack.append(ch)
return "".join(stack)Java
public static String makeGood(String s) {
StringBuilder stack = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (stack.length() > 0) {
char top = stack.charAt(stack.length() - 1);
if (top != c && Character.toLowerCase(top) == Character.toLowerCase(c)) {
stack.deleteCharAt(stack.length() - 1);
continue;
}
}
stack.append(c);
}
return stack.toString();
}C++
string makeGood(string s) {
string stk;
for (char c : s) {
if (!stk.empty()) {
char top = stk.back();
if (top != c && tolower(top) == tolower(c)) {
stk.pop_back();
continue;
}
}
stk.push_back(c);
}
return stk;
}JavaScript
var makeGood = function(s) {
const stack = [];
for (let i = 0; i < s.length; i++) {
const c = s.charAt(i);
if (stack.length > 0) {
const top = stack[stack.length - 1];
if (top !== c && top.toLowerCase() === c.toLowerCase()) {
stack.pop();
continue;
}
}
stack.push(c);
}
return stack.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Stack Data Structure