Scale Engineer

Delete Characters to Make Fancy String

Easy
#1784Time: 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: 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.1 company
Data structures
String
Companies
Wayfair

Prompt

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 <= 105
  • s consists only of lowercase English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem