Watch 10 video solutions for Delete Characters to Make Fancy String, a easy level problem involving String. This walkthrough by codestorywithMIK has 6,897 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105s consists only of lowercase English letters.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 | 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. |