Delete Characters to Make Fancy String

Problem Description

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 will always be unique.

Key Insights

• A fancy string must not contain three consecutive identical characters.
• We can iterate through the string and keep track of the count of consecutive identical characters.
• If the count exceeds 2, we need to skip adding the extra characters to the result.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s, as we traverse the string once. Space Complexity: O(n), for the output string that may store up to n characters in the worst case.

Solution

To solve the problem, we can use a simple iteration approach. We will maintain a result string (or list) and traverse the given string while counting consecutive characters. If we encounter a character that makes the count exceed 2, we will skip adding it to the result. This ensures that we only have at most two consecutive characters in our result.

The algorithm is as follows:

1. Initialize an empty result list to build the fancy string.
2. Traverse the input string and keep a count of consecutive characters.
3. For each character, if the count of that character does not exceed 2, append it to the result list.
4. Finally, convert the result list back to a string and return it.

Code Solutions