Delete Characters to Make Fancy String

Difficulty: Easy | Acceptance: 74.10% | Paid: No Topics: String

A fancy string is a string where no three consecutive characters are equal.

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

Return the final string after the deletion. It can be shown that the answer is unique.

• Examples
• Constraints
• Iterative String Building
• In-place Modification
• Regular Expression

Examples

Input: s = "leeetcode"
Output: "leetcode"
Explanation: Remove an 'e' from the first group of "ee" to get "leetcode".
There are no more than two consecutive characters that are equal, so the answer is "leetcode".

Input: s = "aaabaaaa"
Output: "aabaa"
Explanation: Remove an 'a' from the first group of "aaa" to get "aabaaaa".
Remove two 'a's from the second group of "aaaa" to get "aabaa".
There are no more than two consecutive characters that are equal, so the answer is "aabaa".

Input: s = "aab"
Output: "aab"
Explanation: No three consecutive characters are equal, so no characters need to be removed.
The answer is "aab".

Constraints

1 <= s.length <= 10⁵
s consists only of lowercase English letters.

Iterative String Building

Intuition Build a new string character by character, checking if adding the current character would create three consecutive identical characters.

Steps

• Initialize an empty result list/array
• Iterate through each character in the input string
• For each character, check if the last two characters in the result are the same as the current character
• If yes, skip this character; otherwise, append it to the result
• Return the joined result string

class Solution:
    def makeFancyString(self, 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)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the result string
• Notes: Simple and efficient approach with clear logic

In-place Modification

Intuition Modify the string in-place by tracking the write position and checking for three consecutive characters, avoiding extra space for a new string.

Steps

• Handle edge case where string length is less than 3
• Convert string to a mutable array if needed
• Use a write pointer starting at index 2
• For each character from index 2 onwards, check if it differs from either of the previous two written characters
• If different, write it at the write pointer and increment
• Return the substring up to the write pointer

class Solution:
    def makeFancyString(self, s: str) -> str:
        if len(s) < 3:
            return s
        result = list(s)
        write = 2
        for i in range(2, len(s)):
            if result[i] != result[write - 1] or result[i] != result[write - 2]:
                result[write] = result[i]
                write += 1
        return ''.join(result[:write])

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the character array (O(1) extra space in C++ where strings are mutable)
• Notes: More memory efficient in languages with mutable strings

Regular Expression

Intuition Use regex pattern matching to find and replace sequences of three or more consecutive identical characters with just two of them.

Steps

• Define a regex pattern that matches any character followed by itself two or more times
• Replace each match with just two instances of that character
• Return the resulting string

import re

class Solution:
    def makeFancyString(self, s: str) -> str:
        return re.sub(r'(.)\1\1+', r'\1\1', s)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the result string
• Notes: Very concise one-liner solution but may have higher constant factors due to regex engine overhead