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.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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n). Space Complexity: O(n).
| Approach | Complexity |
|---|---|
| Simple Iterative Check | Time Complexity: |
| Sliding Window Technique | Time Complexity: |
Delete Characters to Make Fancy String | Simple & Easy | Leetcode 1957 | codestorywithMIK • codestorywithMIK • 4,336 views views
Watch 9 more video solutions →Practice Delete Characters to Make Fancy String with our built-in code editor and test cases.
Practice on FleetCode