Problem of The Day: Delete Characters to Make Fancy String

Problem Statement

Intuition

The goal of this algorithm is to remove consecutive characters from a string if they appear three or more times in a row. The idea is to iterate through each character and keep track of the previous character and its count. This helps us decide when to skip adding a character to the result to avoid having three consecutive identical characters.

Approach

1. Initialize an empty list stack to store the resulting characters.
2. Use a variable prev to keep track of the last character added to the result and a count variable to track consecutive occurrences of this character.
3. Iterate through each character c in the string:
   • If c is the same as prev, increase the count.
   • If c is different, reset the count to 1.
   • If count is less than 3, add c to the stack. Otherwise, skip it.
4. Update prev to c after each iteration to reflect the most recent character added to stack.
5. Finally, join the characters in stack to form the final string without any three consecutive identical characters.

Complexity

• Time complexity: (O(n))
  We iterate through each character in the input string s once, where n is the length of the string.

• Space complexity: (O(n))
  The stack list may store up to all characters in s if none are skipped, resulting in an (O(n)) space requirement.

Code

class Solution:
    def makeFancyString(self, s: str) -> str:
        stack = []
        prev = ''
        count = 0
        for c in s:
            if stack:
                if prev == c:
                    count += 1
                else:
                    count = 1
                if count >= 3:
                    continue
            else:
                count = 1
            prev = c
            stack.append(c)
        return ''.join(stack)

Approach 1: Insert characters in a new string

class Solution:
    def makeFancyString(self, s: str) -> str:

        prev = s[0]
        frequency = 1
        ans = s[0]

        for i in range(1, len(s)):
            if s[i] == prev:
                frequency += 1
            else:
                prev = s[i]
                frequency = 1

            if frequency < 3:
                ans += s[i]

        return ans

Approach 2: In-Place Two-Pointer Approach

class Solution:
    def makeFancyString(self, s: str) -> str:
        # If size of string is less than 3, return it.
        if len(s) < 3:
            return s

        # Convert the string to a list for mutability.
        s_list = list(s)
        j = 2

        # Iterate through the string from index 2.
        for i in range(2, len(s)):
            # If the current character is not equal to the previously inserted
            # two characters, then we can add it to the result.
            if s_list[i] != s_list[j - 1] or s_list[i] != s_list[j - 2]:
                s_list[j] = s_list[i]
                j += 1

        # Resize the list to the number of valid characters and join it back into a string.
        return "".join(s_list[:j])