Delete Characters to Make Fancy String — Problem & Solution
Delete Characters to Make Fancy String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Delete Characters to Make Fancy String is a medium coding problem on strings and greedy, asked in Amazon, Google and TCS interviews.
- Difficulty: Medium
- Topics: Strings, Greedy
- Asked at: Amazon, Google, TCS
- 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 fancy if no three consecutive characters are equal.
Delete the minimum number of characters from s to make it fancy and return the result. The answer is unique.
Example 1
Input: s = "cooodekairo"
Output: coodekairo
Explanation: One `o` is dropped from the run of three.
Example 2
Input: s = "aaabaaaa"
Output: aabaa
Explanation: Each run longer than two is trimmed to two.
Example 3
Input: s = "aab"
Output: aab
Explanation: Already fancy.
Constraints
1 <= s.length <= 10^5s consists only of lowercase English letters.
Hints for Delete Characters to Make Fancy String
Hint 1
Build the answer left to right and only look at the last two characters you kept.
Hint 2
Skip the incoming character if those two already equal it.
Hint 3
Equivalently, keep the first two characters of every run and drop the rest.
How to solve Delete Characters to Make Fancy String
Build the result greedily: append each character unless the last two already appended are equal to it. That keeps exactly the first two characters of every run.
Approach
- Start with an empty output.
- For each character of
s, skip it if the output's last two characters both equal it. - Otherwise append it.
Why it works
Deleting from the end of a run rather than the start costs the same and keeps the check local — only the last two kept characters ever matter, so no lookahead or run-boundary bookkeeping is needed. The answer is unique because within a run every character is identical, so which copies are removed is irrelevant; only how many.
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
- Compare against the output being built, not against the original string — deletions shift the context.
- Runs of exactly two are legal and must be kept intact.
- Deleting the whole run is wrong; two copies survive.
Reference solution
Python
def makeFancyString(s: str) -> str:
out = []
for c in s:
if len(out) >= 2 and out[-1] == c and out[-2] == c:
continue
out.append(c)
return "".join(out)Java
public static String makeFancyString(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int n = sb.length();
if (n >= 2 && sb.charAt(n - 1) == c && sb.charAt(n - 2) == c) continue;
sb.append(c);
}
return sb.toString();
}C++
string makeFancyString(string s) {
string out;
for (char c : s) {
size_t n = out.size();
if (n >= 2 && out[n - 1] == c && out[n - 2] == c) continue;
out += c;
}
return out;
}JavaScript
var makeFancyString = function(s) {
var out = "";
for (var i = 0; i < s.length; i++) {
var n = out.length;
var c = s.charAt(i);
if (n >= 2 && out.charAt(n - 1) === c && out.charAt(n - 2) === c) continue;
out += c;
}
return out;
};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 · Greedy Algorithms