LeetCode 1957 - Delete Characters to Make Fancy String

LeetCode Problem 1957

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to transform a given string into a "fancy string". A fancy string is defined as a string that does not contain three consecutive identical characters anywhere in the string.

We are allowed to delete characters from the original string, and our goal is to delete as few characters as possible. After performing the minimum deletions, we return the resulting string.

The input consists of a single string s containing only lowercase English letters. The length of the string can be as large as 10^5, which means the solution must be efficient. Any algorithm with quadratic time complexity would likely be too slow for the worst case.

The important observation is that we only care about runs of repeated characters. Two consecutive identical characters are allowed, but the third consecutive identical character must be removed. For example:

"aa" is valid
"aaa" is invalid
"aabaa" is valid
"baaaab" is invalid because it contains four consecutive 'a' characters

The problem guarantees that the final answer is unique. This happens because the minimum deletion strategy is deterministic: whenever a third identical consecutive character appears, that character must be removed.

Several edge cases are important to consider:

Strings shorter than length 3 are always already fancy.
Strings with no repeated characters require no deletions.
Strings where every character is the same, such as "aaaaaa", require repeated deletions.
Long runs of identical characters, such as "bbbbbbbb", must be reduced to exactly two consecutive characters.

Approaches

Brute Force Approach

A brute force approach could repeatedly scan the string looking for any occurrence of three consecutive identical characters. Whenever such a sequence is found, we delete one character and restart the scan.

For example:

Start with "aaabaaaa"
Detect "aaa" and delete one character
Restart scanning
Detect another invalid sequence
Continue until the string becomes valid

This approach works because eventually all invalid triples are removed. However, deleting characters from the middle of a string is expensive, and repeatedly rescanning the string leads to poor performance.

In the worst case, each deletion could require rebuilding the string, and we may perform many deletions. This can lead to quadratic time complexity.

Optimal Approach

The key insight is that we do not need to repeatedly modify and rescan the string. Instead, we can build the answer incrementally while ensuring that no invalid sequence is ever created.

As we process each character:

If adding the current character would create three consecutive identical characters, we skip it.
Otherwise, we append it to the result.

This greedy strategy is optimal because:

Keeping characters whenever possible minimizes deletions.
The only time we must delete a character is when it would create an invalid triple.

We can efficiently build the result in one pass using a list or string builder.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly rescans and rebuilds the string
Optimal	O(n)	O(n)	Single pass greedy construction

Algorithm Walkthrough

Create an empty result container.

We will build the fancy string character by character. Using a list is efficient because appending is an O(1) operation. 2. Iterate through each character in the input string.

For every character, decide whether it can safely be added to the result. 3. Check the last two characters already in the result.

If the result already ends with two copies of the current character, adding another one would create three consecutive identical characters. 4. Skip invalid characters.

If the current character would create a triple, do not append it. 5. Append valid characters.

Otherwise, add the current character to the result. 6. Convert the result container back into a string.

After processing all characters, the constructed string is guaranteed to satisfy the fancy string condition.

Why it works

The algorithm maintains the invariant that the partially constructed result is always a valid fancy string. Each new character is only added if it does not violate the rule against three consecutive identical characters.

Because we only remove characters when absolutely necessary, the number of deletions is minimized. Therefore, the resulting string is both valid and optimal.

Python Solution

class Solution:
    def makeFancyString(self, s: str) -> str:
        result = []

        for char in s:
            if len(result) >= 2 and result[-1] == char and result[-2] == char:
                continue

            result.append(char)

        return "".join(result)

The implementation uses a list called result to efficiently build the final string.

For each character in the input string:

The code checks whether the last two characters already stored in result are equal to the current character.
If they are, appending the current character would create three consecutive identical characters, so the character is skipped.
Otherwise, the character is appended.

At the end, "".join(result) converts the list into the final string.

This implementation directly follows the greedy algorithm described earlier and processes the input in a single pass.

Go Solution

func makeFancyString(s string) string {
    result := make([]byte, 0, len(s))

    for i := 0; i < len(s); i++ {
        char := s[i]

        n := len(result)

        if n >= 2 && result[n-1] == char && result[n-2] == char {
            continue
        }

        result = append(result, char)
    }

    return string(result)
}

The Go implementation uses a byte slice to efficiently build the resulting string.

Unlike Python lists, Go slices require explicit length management. The code checks the last two elements of the result slice before appending a new character.

Since the input contains only lowercase English letters, using byte is sufficient and efficient.

Worked Examples

Example 1

Input:

s = "leeetcode"

Step	Current Character	Result Before	Action	Result After
1	l	""	append	"l"
2	e	"l"	append	"le"
3	e	"le"	append	"lee"
4	e	"lee"	skip	"lee"
5	t	"lee"	append	"leet"
6	c	"leet"	append	"leetc"
7	o	"leetc"	append	"leetco"
8	d	"leetco"	append	"leetcod"
9	e	"leetcod"	append	"leetcode"

Final result:

"leetcode"

Example 2

Input:

s = "aaabaaaa"

Step	Current Character	Result Before	Action	Result After
1	a	""	append	"a"
2	a	"a"	append	"aa"
3	a	"aa"	skip	"aa"
4	b	"aa"	append	"aab"
5	a	"aab"	append	"aaba"
6	a	"aaba"	append	"aabaa"
7	a	"aabaa"	skip	"aabaa"
8	a	"aabaa"	skip	"aabaa"

Final result:

"aabaa"

Example 3

Input:

s = "aab"

Step	Current Character	Result Before	Action	Result After
1	a	""	append	"a"
2	a	"a"	append	"aa"
3	b	"aa"	append	"aab"

Final result:

"aab"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(n)	The result string may store all input characters

The algorithm performs a single left to right traversal of the input string. Each iteration does only constant time work, so the total running time is linear.

The auxiliary space is linear because the result container may hold up to all characters of the original string when no deletions are needed.

Test Cases

solution = Solution()

assert solution.makeFancyString("leeetcode") == "leetcode"  # example with one deletion
assert solution.makeFancyString("aaabaaaa") == "aabaa"      # multiple deletions
assert solution.makeFancyString("aab") == "aab"             # already valid

assert solution.makeFancyString("a") == "a"                 # single character
assert solution.makeFancyString("aa") == "aa"               # two identical characters allowed
assert solution.makeFancyString("aaa") == "aa"              # remove third identical character
assert solution.makeFancyString("aaaa") == "aa"             # long identical sequence
assert solution.makeFancyString("ababab") == "ababab"       # alternating characters
assert solution.makeFancyString("bbbbccccc") == "bbcc"      # multiple repeated groups
assert solution.makeFancyString("abc") == "abc"             # no repeated characters
assert solution.makeFancyString("xxxyyyzzz") == "xxyyzz"    # repeated triples
assert solution.makeFancyString("aabbaaaaabb") == "aabbaabb" # repeated sequence in middle

Test	Why
`"leeetcode"`	Validates single deletion from repeated group
`"aaabaaaa"`	Validates multiple deletions across groups
`"aab"`	Confirms already valid input remains unchanged
`"a"`	Smallest possible input
`"aa"`	Two consecutive identical characters are allowed
`"aaa"`	Simplest invalid case
`"aaaa"`	Long repeated sequence
`"ababab"`	Alternating characters should remain unchanged
`"bbbbccccc"`	Multiple independent repeated groups
`"abc"`	No duplicates at all
`"xxxyyyzzz"`	Several triple sequences
`"aabbaaaaabb"`	Long repeated section in the middle

Edge Cases

Very Short Strings

Strings of length 1 or 2 can never contain three consecutive identical characters. A buggy implementation might incorrectly try to access the last two characters without checking the current length first.

This implementation safely checks len(result) >= 2 before examining the last two characters.

Long Runs of the Same Character

Inputs such as "aaaaaaaa" are important because they contain many invalid triples. A naive implementation might only remove one extra character and still leave invalid sequences behind.

This algorithm continuously skips every character after the second consecutive occurrence, ensuring the final result becomes "aa".

Multiple Separate Repeated Groups

Inputs like "aaabbbcccaaa" contain several independent repeated sections. Some incorrect solutions may only handle the first invalid sequence.

Because the algorithm processes every character independently while maintaining the fancy string invariant, all repeated groups are handled correctly in a single traversal.