We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Delete Characters to Make Fancy String

Number: 1302

Difficulty: Easy

Paid? No

Companies: Bloomberg, Wayfair

Problem Description

Given a string s, delete the minimum number of characters such that no three consecutive characters are the same. The resulting string must be "fancy" where no three consecutive characters are equal. It can be shown that the answer is unique.

Key Insights

  • The goal is to avoid any group of three identical characters in sequence.
  • A single pass through the string is sufficient by checking the last two characters of the result.
  • If the current character is the same as the last two in the result string, skip it; otherwise, add it.
  • This greedy approach ensures the minimal number of deletions.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, because we process each character once. Space Complexity: O(n), for storing the output result which in worst case is nearly the same size as the input.

Solution

We use a greedy algorithm with a simple iteration over the string. The data structure used is a list (or equivalent in other languages) that acts as a dynamic array to build the final string. For each character in the input string, we check if it would form three consecutive identical characters by comparing against the last two characters stored in the result. If it would, we skip adding it; otherwise, we append it. This ensures that the resulting string is the “fancy” version with minimal deletions.

Code Solutions

# Python solution with line-by-line comments

class Solution:
    def makeFancyString(self, s: str) -> str:
        # Initialize an empty list to build the fancy string
        result = []
        
        # Iterate over each character in the input string
        for char in s:
            # Check if last two characters are the same as the current character
            if len(result) >= 2 and result[-1] == char and result[-2] == char:
                # Skip adding the character to avoid three consecutive identical characters
                continue
            # Append the current character as it doesn't form a triplet
            result.append(char)
        
        # Join the list into a string and return
        return "".join(result)

# Example usage:
# sol = Solution()
# print(sol.makeFancyString("leeetcode"))
← Back to All Questions