Problem

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.

Examples

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".

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Compare last 2 chars in answer

Code

Java
 class Solution {
     public String makeFancyString(String s) {
         StringBuilder ans = new StringBuilder();
         for (int i = 0; i < s.length(); i++) {
             int n = ans.length();
             if (n >= 2 && ans.charAt(n - 1) == s.charAt(i) && ans.charAt(n - 2) == s.charAt(i)) {
                 continue;
             }
             ans.append(s.charAt(i));
         }
         return ans.toString();
     }
 }
Python
class Solution:
    def makeFancyString(self, s: str) -> str:
        ans: list[str] = []
        for ch in s:
            n: int = len(ans)
            if n >= 2 and ans[-1] == ch and ans[-2] == ch:
                continue
            ans.append(ch)
        return ''.join(ans)

Complexity

  • ⏰ Time complexity: O(n), where n is length of input string, as we perform a single iteration through the string s.
  • 🧺 Space complexity: O(n), as we use a list to store up to n characters.

Method 2 - Using the counter

The problem requires us to limit each character to appear at most twice consecutively. To achieve this, we can keep a count (cnt) of how many times the current character has appeared consecutively so far. This count lets us decide if the next character should be added or skipped.

Here is the approach:

  1. Tracking consecutive characters: By starting with the first character of the input string s and iterating through the rest, we can build the result string (ans) one character at a time. This incremental approach allows us to check each character as it arrives, only adding it if it maintains the “fancy” requirement of no three consecutive identical characters.
  2. Switching Between Characters: Whenever a new character (different from the previous one) is encountered, the consecutive count (cnt) is reset, allowing us to add the new character freely. This reset is crucial because a different character means there’s no longer a risk of exceeding two consecutive characters.

Code

Java
class Solution {
    public String makeFancyString(String s) {
        StringBuilder ans = new StringBuilder();
        ans.append(s.charAt(0));
        int n = s.length(), cnt = 1;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == ans.charAt(ans.length() - 1)) {
                cnt++;
                if (cnt < 3) {
                    ans.append(s.charAt(i));
                }
            } else {
                cnt = 1;
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }
}
Python
class Solution:
    def makeFancyString(self, s: str) -> str:
        # List to store the final result
        ans = []
        # Append the first character
        ans.append(s[0])
        # Initialize the counter
        cnt = 1
        # Iterate through the string starting from the second character
        for i in range(1, len(s)):
            if s[i] == ans[-1]:
                # If current character matches last character in result, increment the counter
                cnt += 1
                if cnt < 3:
                    # Only add the character if the count is less than 3
                    ans.append(s[i])
            else:
                # If current character is different, reset the counter and add the character
                cnt = 1
                ans.append(s[i])
        # Join the list into a string and return
        return ''.join(ans)

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)