Problem Description

A fancy string is defined as a string where no three consecutive characters are the same.

Given a string s, you need to delete the minimum possible number of characters from s to make it a fancy string.

Return the final string after the deletion. The answer will always be unique.

For example:

• If s = "aaabaaaa", you would need to remove some as to ensure no three consecutive as exist. The result would be "aabaa".
• If s = "aab", the string is already fancy since there are no three consecutive equal characters, so return "aab".

The solution works by iterating through the string and keeping each character only if:

• It's one of the first two characters (positions 0 or 1), OR
• It's different from the character at position i-1, OR
• It's different from the character at position i-2

This ensures that we never have three consecutive identical characters in the resulting string while removing the minimum number of characters necessary.

Intuition

The key insight is that we want to keep as many characters as possible while ensuring no three consecutive characters are the same. This means we should only remove a character when it would create a sequence of three identical consecutive characters.

Think about it this way: as we build our result string character by character, we need to check if adding the current character would violate the "fancy" property. The violation happens when the current character is the same as both of the two immediately preceding characters.

For any character at position i:

• If i < 2, we don't have enough preceding characters to form a triplet, so we can safely include it
• If the character is different from either s[i-1] or s[i-2], then even if we include it, we won't have three consecutive identical characters

This greedy approach works because we're making the locally optimal choice at each step - we include a character whenever possible and only skip it when absolutely necessary (when it would be the third consecutive identical character). Since we process the string from left to right and make decisions based only on the previous two characters, we ensure we remove the minimum number of characters needed to make the string fancy.

The condition c != s[i - 1] or c != s[i - 2] cleverly captures this logic - if the current character is different from either of the previous two, we're safe to include it. Only when c == s[i-1] == s[i-2] do we skip the character.

Solution Approach

We use a simulation approach to iterate through the string and build our answer character by character.

Data Structure Used:

• An array ans to store the characters that will form our fancy string

Algorithm Steps:

1. Initialize an empty list ans to collect the characters of our result string.

2. Iterate through each character in the string s using enumeration to get both the index i and character c.

3. For each character at position i, check if we should include it:

   • If i < 2: We're at the first or second position, so we can't have three consecutive characters yet. Include the character.
   • If c != s[i - 1]: The current character is different from the previous one, so it won't create three consecutive identical characters. Include it.
   • If c != s[i - 2]: The current character is different from the character two positions back, so even if it matches s[i-1], we won't have three consecutive identical characters. Include it.

4. If any of the above conditions is true, append the character to ans.

5. After processing all characters, join the characters in ans to form the final string using "".join(ans).

Why this works: The condition if i < 2 or c != s[i - 1] or c != s[i - 2] ensures that we only skip a character when i >= 2 AND c == s[i-1] AND c == s[i-2]. This is precisely when adding the current character would create three consecutive identical characters.

Time Complexity: O(n) where n is the length of the input string, as we iterate through the string once.

Space Complexity: O(n) for storing the result in the ans list.

Example Walkthrough

Let's walk through the solution with s = "aaabaaaa":

Initial Setup:

• Input string: "aaabaaaa"
• Result array ans = []

Step-by-step iteration:

1. i=0, c='a':

   • Check: i < 2? Yes (0 < 2)
   • Action: Add 'a' to ans
   • ans = ['a']

2. i=1, c='a':

   • Check: i < 2? Yes (1 < 2)
   • Action: Add 'a' to ans
   • ans = ['a', 'a']

3. i=2, c='a':

   • Check: i < 2? No (2 ≮ 2)
   • Check: c != s[1]? No ('a' == 'a')
   • Check: c != s[0]? No ('a' == 'a')
   • Action: Skip this 'a' (would create "aaa")
   • ans = ['a', 'a']

4. i=3, c='b':

   • Check: i < 2? No
   • Check: c != s[2]? Yes ('b' != 'a')
   • Action: Add 'b' to ans
   • ans = ['a', 'a', 'b']

5. i=4, c='a':

   • Check: i < 2? No
   • Check: c != s[3]? Yes ('a' != 'b')
   • Action: Add 'a' to ans
   • ans = ['a', 'a', 'b', 'a']

6. i=5, c='a':

   • Check: i < 2? No
   • Check: c != s[4]? No ('a' == 'a')
   • Check: c != s[3]? Yes ('a' != 'b')
   • Action: Add 'a' to ans
   • ans = ['a', 'a', 'b', 'a', 'a']

7. i=6, c='a':

   • Check: i < 2? No
   • Check: c != s[5]? No ('a' == 'a')
   • Check: c != s[4]? No ('a' == 'a')
   • Action: Skip this 'a' (would create "aaa")
   • ans = ['a', 'a', 'b', 'a', 'a']

8. i=7, c='a':

   • Check: i < 2? No
   • Check: c != s[6]? No ('a' == 'a')
   • Check: c != s[5]? No ('a' == 'a')
   • Action: Skip this 'a' (would create "aaa")
   • ans = ['a', 'a', 'b', 'a', 'a']

Final Result:

• Join the array: "".join(ans) = "aabaa"
• We removed 3 characters (at indices 2, 6, and 7) to prevent three consecutive 'a's

The algorithm successfully maintains the fancy string property by only skipping characters when they would form a triplet with the two preceding characters.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. The algorithm iterates through each character of the string exactly once using the enumerate function and for loop. Each operation inside the loop (checking conditions and appending to the list) takes O(1) time, resulting in a total time complexity of O(n).

The space complexity is O(n) for the output string stored in the ans list. However, if we exclude the space required for the output (which is necessary to return the result), the space complexity is O(1) as we only use a constant amount of extra space for the loop variables i and c.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Index Checking Logic

The Problem: A common mistake is trying to check characters at result[index - 1] and result[index - 2] instead of s[index - 1] and s[index - 2]. This leads to index out of bounds errors or incorrect comparisons.

Incorrect Implementation:

def makeFancyString(self, s: str) -> str:
    result = []
    for index, char in enumerate(s):
        # WRONG: Checking result array instead of original string
        if len(result) < 2 or char != result[-1] or char != result[-2]:
            result.append(char)
    return "".join(result)

Why It's Wrong: The indices in result don't correspond to the indices in s. When we skip characters, the result array becomes shorter than the original string, making index-based comparisons incorrect.

Correct Approach: Always compare against the original string s using the current index, not against the result array.

Pitfall 2: Using String Concatenation Instead of List

The Problem: Building the result using string concatenation (result += char) instead of a list leads to poor performance.

Inefficient Implementation:

def makeFancyString(self, s: str) -> str:
    result = ""  # Using string instead of list
    for index, char in enumerate(s):
        if index < 2 or char != s[index - 1] or char != s[index - 2]:
            result += char  # String concatenation - O(n) operation
    return result

Why It's Inefficient: Strings are immutable in Python. Each concatenation creates a new string object, copying all previous characters. This turns the overall complexity from O(n) to O(n²).

Solution: Use a list to collect characters and join them at the end. List append operations are O(1) amortized, keeping the overall complexity at O(n).

Pitfall 3: Misunderstanding the Condition Logic

The Problem: Using AND instead of OR in the condition, or negating the logic incorrectly.

Incorrect Implementation:

def makeFancyString(self, s: str) -> str:
    result = []
    for index, char in enumerate(s):
        # WRONG: Using AND instead of OR
        if index < 2 and char != s[index - 1] and char != s[index - 2]:
            result.append(char)
    return "".join(result)

Why It Fails: This would only include characters at positions 0 and 1 if they're different from non-existent previous positions, causing errors or unexpected behavior.

Correct Logic: We want to include a character if ANY of these conditions is true:

• It's at position 0 or 1 (can't form three consecutive yet)
• It differs from the immediate previous character
• It differs from the character two positions back

The OR operator ensures we only exclude a character when ALL conditions for inclusion are false (i.e., when we have three consecutive identical characters).