Delete Characters to Make Fancy String — Medium Problem & Solution

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^5
• s consists only of lowercase English letters.

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

1. Start with an empty output.
2. For each character of s, skip it if the output's last two characters both equal it.
3. 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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Count Number of Homogenous Substrings Medium
• Construct String With Repeat Limit Medium