Delete Characters to Make Fancy String

EASY

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.

Example 1:

Input: s = "leeetcode"
Output: "leetcode"
Explanation:
Remove an 'e' from the first group of 'e's to create "leetcode".
No three consecutive characters are equal, so return "leetcode".

Example 2:

Input: s = "aaabaaaa"
Output: "aabaa"
Explanation:
Remove an 'a' from the first group of 'a's to create "aabaaaa".
Remove two 'a's from the second group of 'a's to create "aabaa".
No three consecutive characters are equal, so return "aabaa".

Example 3:

Input: s = "aab"
Output: "aab"
Explanation: No three consecutive characters are equal, so return "aab".

Constraints:

1 <= s.length <= 10⁵
s consists only of lowercase English letters.

Approaches

Checkout 3 different approaches to solve Delete Characters to Make Fancy String. Click on different approaches to view the approach and algorithm in detail.

Two Pointers (In-place Style)

This approach uses a two-pointer technique to build the result string in a character array. It's a space-optimized variant of the StringBuilder approach, often with better performance due to direct array manipulation and avoiding StringBuilder overhead. This is a classic pattern for filtering an array or string.

Algorithm

Handle the base case: if the string length is less than 3, return the string itself.
Convert the input string s into a character array chars.
Initialize a write pointer j = 2. The first two characters are always kept.
Iterate with a read pointer i from 2 to s.length() - 1.
Inside the loop, check if chars[i] is different from chars[j-1] or chars[j-2].
If the condition is true, it means the character can be kept. Copy the character: chars[j] = chars[i], and then increment j.
After the loop, create a new string from the chars array, using the characters from index 0 up to (but not including) j.
Return the new string.

This method simulates an in-place modification. We convert the input string to a character array. We use two pointers: a read pointer i that scans the original array, and a write pointer j that indicates the end of the valid 'fancy' string being built. The first two characters of the string are always part of the fancy string (if they exist), so we can initialize our result with them and start our pointers i and j from 2. We iterate with i from 2 to the end of the character array. For each character chars[i], we compare it with the last two characters of our valid prefix, which are at chars[j-1] and chars[j-2]. If chars[i] is not equal to both chars[j-1] and chars[j-2], it means we can keep this character. We place it at the j-th position (chars[j] = chars[i]) and advance the write pointer (j++). If chars[i] is the same as the previous two characters, we simply skip it by advancing i without changing j. After the loop, the fancy string is the prefix of the character array of length j. We create a new string from this prefix and return it.

class Solution {
    public String makeFancyString(String s) {
        int n = s.length();
        if (n < 3) {
            return s;
        }
        char[] chars = s.toCharArray();
        int j = 2; // j is the write pointer, points to the next available spot
        for (int i = 2; i < n; i++) { // i is the read pointer
            // We can keep the character if it's not the same as the previous two.
            if (chars[i] != chars[j - 1] || chars[i] != chars[j - 2]) {
                chars[j] = chars[i];
                j++;
            }
        }
        return new String(chars, 0, j);
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the length of the string `s`. We iterate through the character array once. Converting the string to a character array and creating the final string from the array both take O(N) time.Space Complexity: O(N). We create a character array of size N to work with. The final returned string also takes O(N) space. While this is an 'in-place style' algorithm, in Java, it still requires O(N) space due to string immutability. The benefit is mainly in performance constant factors.

Pros and Cons

Pros:

Highly efficient, often faster in practice than StringBuilder due to direct memory access and avoiding object overhead.
A common and useful pattern for array/string filtering problems.
Optimal time complexity.

Cons:

The logic can be slightly more complex to reason about than the straightforward StringBuilder approach.

Code Solutions

Checking out 4 solutions in different languages for Delete Characters to Make Fancy String. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Delete Characters to Make Fancy String

Data Structures:

String

Companies:

Wayfair |