#1957

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Delete Characters to Make Fancy String

This problem asks to remove the minimum number of characters from a string to ensure no three consecutive characters are the same.

string

Problem Statement

A fancy string is defined as a string where no three consecutive characters are the same. Given a string s, your task is to remove the minimum number of characters to make it fancy.

Return the final string after performing the deletions. It is guaranteed that the answer will always be unique.

Examples

Example 1

Input: s = "leeetcode"

Output: "leetcode"

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"

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"

No three consecutive characters are equal, so return "aab".

Constraints

1 <= s.length <= 105
s consists only of lowercase English letters.

Solution Approach

String Traversal

Traverse through the string, checking each character with the previous two. If three consecutive characters are found, skip the current character to avoid triplets.

Efficient In-place Deletion

By using two pointers or a single pass, efficiently delete characters in-place without requiring extra space. This results in an optimal time complexity of O(n).

Edge Case Handling

Ensure proper handling of strings with no consecutive triplets, where no deletions are needed, and cases where deletions are required right from the start.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity of this solution is O(n) because the string is traversed once. The space complexity is O(1) since we do not use extra space besides the input string.

What Interviewers Usually Probe

Candidate demonstrates a clear understanding of how to traverse the string efficiently.
Candidate handles edge cases correctly, ensuring no deletions when unnecessary.
Candidate focuses on the O(n) time complexity and avoids unnecessary space usage.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle edge cases like strings with no triplets.
Not considering the in-place deletion, leading to unnecessary space usage.
Improperly handling the first and last characters, which may not be part of a triplet.

Follow-up variants

Extend the problem to handle uppercase letters as well.
Alter the problem to allow a configurable number of consecutive characters.
Change the problem to return the number of deletions instead of the final string.

FAQ

How can I solve the 'Delete Characters to Make Fancy String' problem?

By traversing the string and removing characters that create consecutive triplets, ensuring no three consecutive characters are the same.

What is the optimal approach to this problem?

The optimal approach is to use a single pass through the string while checking consecutive characters and removing those that would create triplets.

Can the 'Delete Characters to Make Fancy String' problem be solved in constant space?

Yes, it can be solved in O(1) space by modifying the string in-place during traversal.

What are the time and space complexities of this problem?

The time complexity is O(n), and the space complexity is O(1), making this solution very efficient.

What common mistakes should I avoid in this problem?

Avoid unnecessary space usage, forgetfulness with edge cases, and incorrect handling of the first and last characters.

terminal

Solution

Solution 1: Simulation

We can iterate through the string $s$ and use an array $\textit{ans}$ to record the current answer. For each character $\textit{s[i]}$, if $i < 2$ or $s[i]$ is not equal to $s[i - 1]$, or $s[i]$ is not equal to $s[i - 2]$, we add $s[i]$ to $\textit{ans}$.

1

2

3

4

5

6

7

class Solution:
    def makeFancyString(self, s: str) -> str:
        ans = []
        for i, c in enumerate(s):
            if i < 2 or c != s[i - 1] or c != s[i - 2]:
                ans.append(c)
        return "".join(ans)

Continue Practicing

#1960 maximum product of the length of two palindromic substrings #1961 check if string is a prefix of array #1963 minimum number of swaps to make the string balanced