Delete Characters to Make Fancy String - Solution & Explanation
Problem Statement
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 <= 105sconsists only of lowercase English letters.
Approach Overview
Problem Overview: You are given a string s. A string is considered fancy if it does not contain three identical consecutive characters. The task is to delete the minimum number of characters so the final string never has a substring like "aaa" or "bbb".
Approach 1: Simple Iterative Check (O(n) time, O(n) space)
Scan the string from left to right while building a result string. For each character, check the last two characters already placed in the result. If both match the current character, skip it; otherwise append it. The key insight: you only need to track the last two characters to prevent three consecutive duplicates. This works well because the constraint is strictly about consecutive repetition, not global frequency.
This approach uses straightforward iteration and conditional checks, which makes it easy to implement in any language. The algorithm processes each character once, giving O(n) time complexity. The result buffer stores up to n characters, so the space complexity is O(n). Since the logic revolves around sequential processing of a string, it fits naturally with typical string manipulation patterns.
Approach 2: Sliding Window Technique (O(n) time, O(n) space)
The same constraint can also be modeled with a sliding window. Maintain a window representing the current streak of identical characters. As you iterate through the string, extend the window when the current character matches the previous one. If the window size reaches three, skip that character instead of adding it to the result. Otherwise, append it and continue.
This approach treats consecutive identical characters as a dynamic window. When the character changes, reset the streak count to one. The sliding window interpretation clarifies why the algorithm works: you enforce a maximum window size of two for identical characters. Time complexity remains O(n) because each character is visited once, and space complexity is O(n) for the output string. It’s conceptually similar to patterns seen in two pointers or window-based string problems.
Recommended for interviews: The simple iterative check is the approach interviewers expect. It shows you recognize that only the previous two characters matter, leading to a clean O(n) pass. Mentioning the sliding window perspective demonstrates deeper pattern recognition across string and window problems.
Approach 1: Simple Iterative Check
This approach involves inspecting characters in the string one by one and checking the last two characters of the resulting string being constructed. If three consecutive characters are found, the current character is skipped, effectively removing it. This ensures that no three consecutive identical characters are present in the resulting string.
Each character of the input string is added to a new string, checking if it should be added by comparing with the last two characters of the newly created string. This avoids three consecutive repetitions. Memory is manually managed in C using malloc and free.
Complexity
Time Complexity: O(n), where n is the length of the string, as we iterate through the string once. Space Complexity: O(n) due to space required to generate the result string.
Approach 2: Sliding Window Technique
This approach uses a sliding window to keep track of the count of consecutive characters. If the count reaches three, we skip adding the current character to the result. This takes advantage of window logic to efficiently manage consecutive character tracking with minimal operations.
This C implementation uses a counter to track the number of consecutive identical characters. Every time a character is added, it checks if the three consecutive rule is broken, allowing only up to two identical characters consecutively.
Complexity
Time Complexity: O(n). Space Complexity: O(n).
Approach 3: Simulation
We can iterate through the string s and use an array ans to record the current answer. For each character s[i], if i < 2 or s[i] is not equal to s[i - 1], or s[i] is not equal to s[i - 2], we add s[i] to ans.
Finally, we concatenate the characters in ans to get the answer.
The time complexity is O(n), where n is the length of the string s. Ignoring the space consumption of the answer, the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
JavaScript
PHP
Complexity Comparison
| Approach | Complexity |
|---|---|
| Simple Iterative Check | Time Complexity: |
| Sliding Window Technique | Time Complexity: |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Iterative Check | O(n) | O(n) | Best general solution. Clean logic and minimal checks when building the result string. |
| Sliding Window Technique | O(n) | O(n) | Useful when framing the problem as controlling a window of repeating characters. |
Video Solution
Delete Characters to Make Fancy String | Simple & Easy | Leetcode 1957 | codestorywithMIK • codestorywithMIK • 7,075 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Delete Characters to Make Fancy String easy or hard?
Delete Characters to Make Fancy String Python/Java solution
How to solve Delete Characters to Make Fancy String in O(n)?
What is the best approach for Delete Characters to Make Fancy String?
Is Delete Characters to Make Fancy String asked at Google/Amazon/Meta?
What data structure is used in Delete Characters to Make Fancy String?
What is the time complexity of Delete Characters to Make Fancy String?
Ready to solve this problem?
Practice Delete Characters to Make Fancy String with our built-in code editor and test cases.
Practice on FleetCode