Make A Fancy String: How To Delete Characters

Have you ever encountered a string that just felt a bit too repetitive? Like, imagine seeing "aaabbbccc" – it’s valid, sure, but maybe you’d prefer something a little more streamlined, like "aabbcc"? That's precisely the kind of scenario we're diving into with the LeetCode problem "Delete Characters to Make Fancy String" (Problem 1957). It’s all about taking a given string and trimming it down so that no character appears three or more times consecutively. It sounds simple, but as with many coding challenges, the devil is in the details, and finding an efficient solution is key.

This isn't just about making strings look pretty; it’s a fundamental exercise in string manipulation and algorithmic thinking. We’ll explore how to approach this problem, break down a common and effective solution using Java, and discuss why it works so well. Whether you’re a seasoned coder or just starting your journey, understanding these concepts will definitely level up your problem-solving toolkit. Let’s get this fancy string party started!

Understanding the "Fancy String" Concept

So, what exactly makes a string "fancy" in the context of this problem? The rule is straightforward: a string is considered fancy if it does not contain any character that repeats three or more times in a row. Think of it as a rule against excessive repetition. For instance, in the string "leeetcode", the three consecutive 'e's break the fancy rule. The goal, therefore, is to modify the string by deleting the minimum number of characters necessary to eliminate any such sequences of three or more identical characters. The problem statement clearly illustrates this with examples: "leeetcode" becomes "leetcode", and "aaabaaaa" transforms into "aabaa". The latter example is particularly insightful, showing that we might need to remove characters from multiple sequences within the same string to achieve the desired fancy state.

It's important to note that the problem asks us to return a fancy string, not necessarily the only possible fancy string. This implies that there might be multiple ways to achieve the goal, but any valid outcome is acceptable. The most intuitive approach is usually to remove only the extra characters that cause the violation. For "leeetcode", we see a sequence of three 'e's. To make it fancy, we just need to remove one 'e' to get "leetcode". For "aaabaaaa", we have a sequence of four 'a's at the beginning and another sequence of four 'a's at the end. We can remove one 'a' from the first group to get "aabaaaa", and then remove two 'a's from the second group to get "aabaa". This strategy adheres to the principle of making minimal changes while satisfying the condition.

Understanding this core requirement is the first step. Once we grasp what a "fancy string" is and what we need to achieve, we can start thinking about how to implement a solution. The key challenge lies in efficiently identifying and handling these consecutive character sequences. We need a method that can process the string character by character and make decisions on the fly without requiring multiple passes or overly complex data structures. The solution should also be mindful of performance, especially when dealing with potentially long input strings.

A Practical Approach: Iteration and Building a New String

When tackling the "Delete Characters to Make Fancy String" problem, a common and highly effective strategy involves iterating through the input string and building a new string that adheres to the fancy string rules. Instead of trying to modify the original string in place (which can be inefficient in many languages due to string immutability), we create a result string or a mutable string builder and append characters to it only if they maintain the fancy property. This approach simplifies the logic considerably.

Let's consider the input string s. We can initialize an empty string builder, let’s call it sb. We then iterate through each character c of the input string s. For each character, we need to decide whether to append it to sb. The crucial condition to check is: would appending c to sb create a sequence of three identical characters? To determine this, we only need to look at the last two characters already present in sb.

Specifically, if sb has at least two characters, and the last character in sb is the same as c, and the second-to-last character in sb is also the same as c, then appending c would violate the fancy string rule. In this scenario, we simply skip the current character c and move on to the next character in the input string s. If this condition is not met, it means appending c will not create a forbidden sequence of three identical characters, so we append c to sb.

After iterating through all characters in s, the string builder sb will contain the resulting fancy string. We then convert sb back to a standard string and return it. This method is efficient because appending to a string builder is typically an O(1) operation on average, and we process each character of the input string exactly once. The overall time complexity is therefore O(N), where N is the length of the input string.

This iterative building approach is elegant because it directly enforces the rule as we construct the output. It avoids the complexities of searching for violations in an existing string and then figuring out which character to remove. By only adding characters that maintain the fancy property, we guarantee that the final result will be a valid fancy string. This method also handles edge cases gracefully, such as empty strings or strings shorter than three characters, as the conditions for skipping a character will naturally not be met.

Implementing the Solution in Java

Let's translate the iterative building approach into a concrete Java implementation. The provided solution uses a StringBuilder for efficient string construction, which is a standard practice in Java when you need to perform multiple modifications or appends to a string.

class Solution {
    public String makeFancyString(String s) {
        // If the string is shorter than 3 characters, it can't have 3 consecutive same chars.
        if (s.length() < 3) {
            return s;
        }

        // Use StringBuilder for O(1) appends
        StringBuilder sb = new StringBuilder();

        for (char c : s.toCharArray()) {
            int len = sb.length();
            
            // Check if adding the current character 'c' would create 3 consecutive same characters
            if (len >= 2 && sb.charAt(len - 1) == c && sb.charAt(len - 2) == c) {
                // Do nothing (skip this character)
                continue;
            }
            
            // Otherwise, append it to the result
            sb.append(c);
        }

        return sb.toString();
    }
}

The code starts with a crucial base case: if the input string s has a length less than 3, it's impossible to have three consecutive identical characters. In such cases, the string is already fancy by definition, so we can return it directly. This check prevents potential index out-of-bounds errors in the subsequent logic and is an efficient optimization.

Next, a StringBuilder object named sb is initialized. This object will be used to construct the fancy string piece by piece. We then iterate through each character c of the input string s using an enhanced for loop, which conveniently converts s into a character array s.toCharArray().

Inside the loop, for each character c, we first get the current length of the StringBuilder (len = sb.length()). The core logic lies in the if condition: if (len >= 2 && sb.charAt(len - 1) == c && sb.charAt(len - 2) == c). This condition checks two things:

1. len >= 2: Ensures that there are at least two characters already in the StringBuilder. We need at least two characters to check for a potential sequence of three.
2. sb.charAt(len - 1) == c && sb.charAt(len - 2) == c: Checks if the last character (sb.charAt(len - 1)) and the second-to-last character (sb.charAt(len - 2)) in the StringBuilder are both identical to the current character c we are considering.

If this entire if condition evaluates to true, it means appending c would result in three consecutive identical characters. Therefore, we continue to the next iteration of the loop, effectively skipping the current character c.

If the if condition is false (meaning either sb has fewer than two characters, or the last two characters are not both equal to c), then it's safe to append c to our StringBuilder using sb.append(c). This step ensures that we only add characters that maintain the fancy string property.

Finally, after the loop has processed all characters from the input string s, sb.toString() is called to convert the StringBuilder back into a standard Java String, which is then returned as the result. This implementation is clean, efficient, and correctly solves the problem by iteratively building the fancy string.

Why This Solution Works: Efficiency and Correctness

The provided Java solution is a great example of how a well-thought-out iterative approach can solve string manipulation problems elegantly and efficiently. Let's break down why this method is both correct and performs well.

Correctness: The fundamental principle behind the solution's correctness is its greedy nature. At each step, when considering a character from the input string, the algorithm makes the locally optimal choice: append the character if and only if it does not violate the