1957: Delete Characters to Make Fancy String

Problem Statement

A fancy string is defined as a string where no three consecutive characters are identical. Given a string s, your task is to delete the minimum number of characters to make it fancy. Return the final string after deletion. The answer is guaranteed to be unique.

Key Insight

The problem requires removing the minimum characters to ensure no three identical characters appear consecutively. The optimal solution is to:

1. Traverse the string while building the result
2. Keep at most two consecutive identical characters
3. Skip any character that would form a third consecutive identical character

Optimal Approach: Single Pass Filtering

Build the result string by iterating through each character while tracking consecutive counts.

Algorithm Steps

1. Initialize an empty list/string builder for the result
2. Iterate through each character in the input string
3. For each character:
   • If result length ≥ 2 and last two characters are same as current: skip
   • Otherwise: append to result
4. Return the built result

Complexity Analysis

Where n is the length of the string. We traverse the string once and store the result.

class Solution {
public:
    string makeFancyString(string s) {
        string result;
        for (char c : s) {
            int n = result.size();
            if (n >= 2 && result[n-1] == c && result[n-2] == c) {
                continue;
            }
            result.push_back(c);
        }
        return result;
    }
};

class Solution {
    public String makeFancyString(String s) {
        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            int n = result.length();
            if (n >= 2 && 
                result.charAt(n-1) == c && 
                result.charAt(n-2) == c) {
                continue;
            }
            result.append(c);
        }
        return result.toString();
    }
}

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)

Alternative Approach: Two Pointers

Modify the string in-place using two pointers for reduced space complexity.

Algorithm Steps

1. Convert string to character array
2. Initialize two pointers: writer (current position) and count (consecutive count)
3. Iterate with reader pointer:
   • If same as previous: increment count
   • Else: reset count to 1
   • If count < 3: write character and advance writer
4. Return substring up to writer index

Complexity Analysis

class Solution {
public:
    string makeFancyString(string s) {
        int writer = 0, count = 0;
        for (int reader = 0; reader < s.size(); ++reader) {
            if (reader > 0 && s[reader] == s[reader-1]) {
                count++;
            } else {
                count = 1;
            }
            if (count < 3) {
                s[writer++] = s[reader];
            }
        }
        return s.substr(0, writer);
    }
};

class Solution {
    public String makeFancyString(String s) {
        char[] chars = s.toCharArray();
        int writer = 0, count = 0;
        for (int reader = 0; reader < chars.length; reader++) {
            if (reader > 0 && chars[reader] == chars[reader-1]) {
                count++;
            } else {
                count = 1;
            }
            if (count < 3) {
                chars[writer++] = chars[reader];
            }
        }
        return new String(chars, 0, writer);
    }
}

class Solution:
    def makeFancyString(self, s: str) -> str:
        chars = list(s)
        writer = 0
        count = 0
        for reader in range(len(chars)):
            if reader > 0 and chars[reader] == chars[reader-1]:
                count += 1
            else:
                count = 1
            if count < 3:
                chars[writer] = chars[reader]
                writer += 1
        return ''.join(chars[:writer])

Edge Cases and Testing

1. Short Strings (Length < 3)

Input: "a" → Output: "a"
Input: "aa" → Output: "aa"

2. No Consecutive Triplets

Input: "abc" → Output: "abc"

3. Multiple Consecutive Groups

Input: "aaaabbbcccddd" → Output: "aabbccdd"

4. All Identical Characters

Input: "aaaaa" → Output: "aa"

5. Mixed Characters

Input: "aabbccddeee" → Output: "aabbccddee"

Frequently Asked Questions