Remove the minimum number of characters so that no three consecutive characters in the string are the same.
Delete Characters To Make Fancy String
Given a string s, delete some characters so that the resulting string is fancy.
A string is fancy if it does not contain three identical characters in a row. In other words, for every index i >= 2, it must be true that not all of s[i], s[i-1], and s[i-2] are equal.
Return any fancy string obtained by deleting the fewest possible characters.
Because only deletions are allowed, the answer should preserve the original order of the remaining characters.
Input Format
- A single string
s.
Output Format
- Return the fancy string after removing the minimum number of characters.
Constraints
1 <= s.length <= $10^{5}$sconsists of lowercase English letters.
Hints
- Scan the string from left to right and keep track of the last few characters you decided to keep.
- If adding the current character would create three equal characters in a row, skip it.
Input Format
- A single string
s.
Output Format
- The lexicographically arbitrary fancy string formed by deleting the minimum number of characters while preserving order.
Constraints
1 <= s.length <= $10^{5}$scontains only lowercase English letters.
Example 1
Input
s = "leeetcode"
Output
"leetcode"
Explanation
The original string has three consecutive 'e' characters. Deleting one 'e' makes it fancy.
Example 2
Input
s = "aaabaaaa"
Output
"aabaa"
Explanation
Keep at most two equal characters in a row. Removing the extra 'a' characters yields a fancy string with minimal deletions.
Show 1 more example
Example 3
Input
s = "aab"
Output
"aab"
Explanation
There are no three equal consecutive characters, so no deletion is needed.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.