Code Implementation

class Solution:
    def makeFancyString(self, s: str) -> str:
        if not s:
            return ""
        res = [s[0]]
        count = 1
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                count += 1
            else:
                count = 1
            if count <= 2:
                res.append(s[i])
        return "".join(res)
      

class Solution {
public:
    string makeFancyString(string s) {
        if (s.empty()) return "";
        string res;
        res.push_back(s[0]);
        int count = 1;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == s[i-1]) {
                count++;
            } else {
                count = 1;
            }
            if (count <= 2) {
                res.push_back(s[i]);
            }
        }
        return res;
    }
};
      

class Solution {
    public String makeFancyString(String s) {
        if (s == null || s.length() == 0) return "";
        StringBuilder res = new StringBuilder();
        res.append(s.charAt(0));
        int count = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i-1)) {
                count++;
            } else {
                count = 1;
            }
            if (count <= 2) {
                res.append(s.charAt(i));
            }
        }
        return res.toString();
    }
}
      

var makeFancyString = function(s) {
    if (!s.length) return "";
    let res = s[0];
    let count = 1;
    for (let i = 1; i < s.length; i++) {
        if (s[i] === s[i-1]) {
            count++;
        } else {
            count = 1;
        }
        if (count <= 2) {
            res += s[i];
        }
    }
    return res;
};
      

Problem Description

You are given a string s. Your task is to delete the minimum number of characters from s so that no three consecutive characters in the resulting string are identical. In other words, after your deletions, for any index i in the string, it must not be true that s[i] == s[i+1] == s[i+2].

You must return any valid string that satisfies this property. The solution must preserve the order of the remaining characters.

Constraints:

• 1 ≤ s.length ≤ 10⁵
• s consists only of lowercase English letters.

Thought Process

The key challenge is to ensure that no three identical characters appear consecutively. A brute-force approach might involve checking every possible deletion, but this quickly becomes infeasible for large strings.

Instead, we can process the string from left to right, keeping track of how many consecutive times the current character has appeared. If a character appears less than three times in a row, we keep it; if it would make three in a row, we skip (delete) it.

By using a simple counter, we can efficiently decide whether to keep or remove each character, ensuring that the resulting string is "fancy" as required.

Solution Approach

Here is the step-by-step algorithm to solve the problem:

1. Initialize an empty result container (such as a list or string builder).
2. Start by adding the first character of s to the result, since a single character can never violate the rule.
3. Maintain a counter to keep track of consecutive identical characters.
4. Iterate over s starting from the second character:
   • If the current character is the same as the previous one, increment the counter.
   • If it is different, reset the counter to 1.
   • If the counter is less than or equal to 2, append the current character to the result.
   • If the counter exceeds 2, skip appending (effectively deleting the character).
5. After processing all characters, join the result container into a string and return it.

This approach ensures we only keep at most two consecutive identical characters, efficiently building the required "fancy" string in a single pass.

Example Walkthrough

Let's walk through an example with the input s = "aaabaaaa".

• Start with res = ['a'], count = 1
• Next character is 'a' (same as previous): count = 2, append 'a' (res = ['a', 'a'])
• Next character is 'a' (same as previous): count = 3, skip (do not append)
• Next character is 'b' (different): count = 1, append 'b' (res = ['a', 'a', 'b'])
• Next character is 'a' (different): count = 1, append 'a' (res = ['a', 'a', 'b', 'a'])
• Next character is 'a' (same as previous): count = 2, append 'a' (res = ['a', 'a', 'b', 'a', 'a'])
• Next character is 'a' (same as previous): count = 3, skip
• Next character is 'a' (same as previous): count = 4, skip

The final result is "aabaa", which contains no three consecutive identical characters.

Time and Space Complexity

Brute-force approach: Trying all possible deletions would involve checking all subsets of the string, leading to exponential time complexity, which is not feasible for large inputs.

Optimized approach (as implemented):

• Time Complexity: O(n), where n is the length of s. We process each character exactly once.
• Space Complexity: O(n), since we use a result container to store the output string.

Summary

To solve the "Delete Characters to Make Fancy String" problem, we use a simple linear scan with a counter to ensure that no three identical characters appear consecutively. This approach is both efficient and easy to implement, requiring only a single pass through the string and minimal extra memory. The key insight is that by always allowing at most two consecutive identical letters, we guarantee the desired property, making the solution both elegant and optimal.