Delete Characters to Make Fancy String: Greedy Filtering

LeetCode 1957, Delete Characters to Make Fancy String, defines a "fancy" string as one where no three consecutive characters are equal. Given a string s, you need to delete the minimum number of characters so that the result is fancy, and return the resulting string.

For example, "leeetcode" becomes "leetcode" (remove one 'e'), and "aaabaaaa" becomes "aabaa" (remove one 'a' from the first group and two from the second).

Why this problem matters

This problem teaches a core filtering technique: scanning a sequence left to right and deciding whether to include each element based on what you have already collected. You will see this same pattern in problems that remove duplicates, compress strings, or enforce constraints on adjacent elements. The simplicity of the rule (never allow three in a row) makes it a great entry point for learning greedy character-by-character construction.

The brute force approach

You could try generating all possible subsequences of the string and picking the longest one that qualifies as "fancy." But the number of subsequences is exponential, so this blows up immediately. Another brute force idea is to repeatedly scan the string for any triple of consecutive equal characters, remove one, and repeat until no triples remain. That works but runs in O(n^2) time in the worst case because each scan and removal takes O(n), and you might need O(n) removals.

Neither approach is necessary. The problem has a clean one-pass solution.

The key insight: build the result greedily

Instead of modifying the original string, build a new result character by character. For each character in the input, check whether appending it would create three consecutive equal characters at the end of the result. If it would, skip it. If it would not, append it.

This works because the decision at each position is purely local. You only need to look at the last two characters of the result to decide whether the current character is safe to include. There is no benefit to "saving" a deletion for later, so the greedy choice is always optimal.

Walking through it step by step

Let's trace the algorithm on the input "aaaab". At each step, we decide whether the current character can be appended to the result without creating three consecutive equal characters.

The greedy solution

def make_fancy_string(s: str) -> str:
    result = []
    for c in s:
        if len(result) >= 2 and result[-1] == c and result[-2] == c:
            continue
        result.append(c)
    return "".join(result)

The function iterates through each character in the string. For each character c, it checks whether the last two entries in result are both equal to c. If they are, adding c would create a run of three, so the loop skips it with continue. Otherwise, it appends c to the result list. After processing every character, it joins the list into a string and returns it.

Using a list instead of string concatenation is important. Appending to a Python list is amortized O(1), while concatenating strings repeatedly would create a new string each time, turning the solution into O(n^2).

Complexity analysis

Building blocks

1. Greedy character filtering

The core pattern here is a one-pass filter: iterate through a sequence, and for each element decide on the spot whether to include it in the output. The decision is based on a simple local condition, not on any global optimization. This same pattern appears in problems like removing duplicates from sorted arrays, compressing runs of characters, and filtering elements that violate adjacency constraints.

2. Consecutive-count tracking

Rather than maintaining an explicit counter variable, this solution checks the last two characters of the result directly. That is equivalent to tracking whether the consecutive count has reached two. In variations of this problem where the threshold is higher (say, allow up to k consecutive duplicates), you might switch to an explicit counter that resets when the character changes.

Edge cases

Already fancy. If the input has no three consecutive equal characters, every character passes the filter and the output equals the input. The algorithm handles this naturally with no special case.

Single character or two characters. Strings of length 1 or 2 can never violate the fancy condition. The len(result) >= 2 guard ensures you never check result[-1] or result[-2] when the result is too short.

Entire string is the same character. For input "aaaaaa", only the first two 'a's pass the filter. The result is "aa". Every subsequent 'a' gets skipped because the last two result characters are always 'a'.

Alternating characters. For input "ababab", no character ever matches the two before it, so nothing gets removed. The greedy check fires and passes every time.

Common mistakes

Checking the input instead of the result. Some people check whether the current character matches the two previous characters in the original input string. That is wrong because deleted characters shift the positions. You need to check the result you are building, not the source.

Using string concatenation instead of a list. In Python, result += c inside a loop creates a new string object each time. This turns an O(n) algorithm into O(n^2). Always build into a list and join at the end.

Off-by-one on the length check. Forgetting the len(result) >= 2 guard causes an index error when the result has zero or one characters. The condition must be checked before accessing result[-1] and result[-2].

From understanding to recall

You can follow this solution and see why it works. The logic is clean: one loop, one condition, one append-or-skip decision. But when you sit down for an interview in two weeks, will the exact condition (len(result) >= 2 and result[-1] == c and result[-2] == c) come to you without hesitation? Will you remember to build into a list instead of concatenating strings?

Spaced repetition locks in these details. Instead of re-reading the full walkthrough, you drill the individual building blocks (greedy filter pattern, tail-of-result check, list-then-join idiom) at increasing intervals. After a few reps spread across days, the pattern is in long-term memory and you can reproduce it under pressure.

Related posts

• Remove Duplicates from Sorted Array - Similar in-place filtering pattern
• Remove Element - Another greedy element removal problem

CodeBricks helps you move from "I understand it" to "I can do it cold." Every problem you practice gets scheduled for review at the right time, so you build lasting fluency with the patterns that actually show up in interviews.