Is Delete Characters to Make Fancy String easy or hard?

Delete Characters to Make Fancy String is classified as an Easy problem on LeetCode. The challenge focuses on recognizing that only the previous two characters matter, which allows a clean linear scan solution.

Delete Characters to Make Fancy String Python/Java solution

Both Python and Java solutions follow the same logic: iterate through the string and append characters only if they do not create three identical consecutive characters. The implementation uses a result string or StringBuilder and runs in O(n) time.

How to solve Delete Characters to Make Fancy String in O(n)?

Iterate through the string while maintaining a result buffer. Before appending a character, check whether the last two characters in the result match it. If they do, skip the character; otherwise append it. This single pass guarantees O(n) time complexity.

What is the best approach for Delete Characters to Make Fancy String?

The best approach is a simple iterative scan that builds the result string while checking the last two characters already added. If the current character would create three identical consecutive characters, skip it. This solution runs in O(n) time and uses O(n) space for the output.

Is Delete Characters to Make Fancy String asked at Google/Amazon/Meta?

String manipulation and consecutive character constraint problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations that limit repeating characters or enforce substring constraints are common screening questions.

What data structure is used in Delete Characters to Make Fancy String?

The primary structure is a string or dynamic character buffer used to build the result. The algorithm only needs access to the last two characters of this buffer, making it a straightforward string processing problem.

What is the time complexity of Delete Characters to Make Fancy String?

The optimal solution runs in O(n) time because each character in the string is processed exactly once. The space complexity is O(n) since a new result string is constructed while filtering out invalid characters.

Description Hints 2 Solution Video 7:14

1957. Delete Characters to Make Fancy String

Easy74.1% acceptance6 companies

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 <= 10⁵
s consists only of lowercase English letters.

Asked at 6 companies

Wayfair

Google Amazon Microsoft Meta Bloomberg

Topics

String

Hints open one at a time

Hint 1

What's the optimal way to delete characters if three or more consecutive characters are equal?

Hint 2

If three or more consecutive characters are equal, keep two of them and delete the rest.

7:14

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution