Delete Characters to Make Fancy String solution and explanation
Google
9 more videos on this problem
Delete Characters to Make Fancy String | Simple & Easy | Leetcode 1957 | codestorywithMIKcodestorywithMIK · 7:14 · 7K views
1957. Delete Characters to Make Fancy String | Leetcode Daily - PythonLeetcode Daily · 6:12 · 551 views
Daily Leetcode #1938: Jul 21, 2025 - 1957. Delete Characters to Make Fancy StringProgramming Live with Larry · 5:24 · 399 views
Leetcode 1957: Delete Characters to Make Fancy StringAlgorithms Casts · 5:57 · 326 views
Leetcode 1957 Delete Characters to Make Fancy StringMath Geeks · 1:38 · 191 views
1957. Delete Characters to Make Fancy String - leetcode Solution with Manim Visualization.Gautham Gali · 2:10 · 66 views
LeetCode 1957: Delete Characters to Make Fancy String | Python Solution | String ManipulationCode Scribbler · 4:43 · 54 views
Leetcode 1957 | Delete Characters to Make Fancy Stringcodefou · 9:06 · 51 views
Leetcode 1957 | Delete Characters to Make Fancy String | Problem-Solving | Competitive ProgrammingCode Crack · 3:53 · 48 views
1957. Delete Characters to Make Fancy Strings | Java | Leetcode |JavAttack · 5:54 · 33 views
The 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.
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 <= 105sconsists only of lowercase English letters.
Approach overview
Problem Overview: You are given a string s. A string is considered fancy if it does not contain three identical consecutive characters. The task is to delete the minimum number of characters so the final string never has a substring like "aaa" or "bbb".
Approach 1: Simple Iterative Check (O(n) time, O(n) space)
Scan the string from left to right while building a result string. For each character, check the last two characters already placed in the result. If both match the current character, skip it; otherwise append it. The key insight: you only need to track the last two characters to prevent three consecutive duplicates. This works well because the constraint is strictly about consecutive repetition, not global frequency.
This approach uses straightforward iteration and conditional checks, which makes it easy to implement in any language. The algorithm processes each character once, giving O(n) time complexity. The result buffer stores up to n characters, so the space complexity is O(n). Since the logic revolves around sequential processing of a string, it fits naturally with typical string manipulation patterns.
Approach 2: Sliding Window Technique (O(n) time, O(n) space)
The same constraint can also be modeled with a sliding window. Maintain a window representing the current streak of identical characters. As you iterate through the string, extend the window when the current character matches the previous one. If the window size reaches three, skip that character instead of adding it to the result. Otherwise, append it and continue.
This approach treats consecutive identical characters as a dynamic window. When the character changes, reset the streak count to one. The sliding window interpretation clarifies why the algorithm works: you enforce a maximum window size of two for identical characters. Time complexity remains O(n) because each character is visited once, and space complexity is O(n) for the output string. It’s conceptually similar to patterns seen in two pointers or window-based string problems.
Recommended for interviews: The simple iterative check is the approach interviewers expect. It shows you recognize that only the previous two characters matter, leading to a clean O(n) pass. Mentioning the sliding window perspective demonstrates deeper pattern recognition across string and window problems.
Approach 1: Simple Iterative Check
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.
def make_fancy_string(s: str) -> str:
result = []
for c in s:
if len(result) >= 2 and result[-1] == c and result[-2] == c:
continue
result.append(c)
return ''.join(result)
s = "aabaa"
print(make_fancy_string(s))public class MakeFancyString {
public static String makeFancyString(String s) {
StringBuilder result = new StringBuilder();
for (char c : s.toCharArray()) {
if (result.length() >= 2 && result.charAt(result.length() - 1) == c && result.charAt(result.length() - 2) == c) {
continue;
}
result.append(c);
}
return result.toString();
}
public static void main(String[] args) {
String s = "aabaa";
System.out.println(makeFancyString(s));
}
}#include <iostream>
#include <string>
std::string makeFancyString(const std::string& s) {
std::string result;
for (char c : s) {
if (result.size() >= 2 && result[result.size() - 1] == c && result[result.size() - 2] == c) {
continue;
}
result += c;
}
return result;
}
int main() {
std::string s = "aabaa";
std::cout << makeFancyString(s) << std::endl;
return 0;
}function makeFancyString(s) {
let result = [];
for (let i = 0; i < s.length; i++) {
if (result.length >= 2 && result[result.length - 1] === s[i] && result[result.length - 2] === s[i]) {
continue;
}
result.push(s[i]);
}
return result.join('');
}
let s = "aabaa";
console.log(makeFancyString(s));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* makeFancyString(char* s) {
size_t len = strlen(s);
char* result = (char*)malloc(len + 1);
int index = 0;
for (int i = 0; i < len; i++) {
if (index >= 2 && result[index - 1] == s[i] && result[index - 2] == s[i]) {
continue;
}
result[index++] = s[i];
}
result[index] = '\0';
return result;
}
int main() {
char s[] = "aabaa";
char* result = makeFancyString(s);
printf("%s", result);
free(result);
return 0;
}using System;
using System.Text;
class MakeFancyString {
static string MakeFancy(string s) {
StringBuilder result = new StringBuilder();
foreach (char c in s) {
if (result.Length >= 2 && result[result.Length - 1] == c && result[result.Length - 2] == c) {
continue;
}
result.Append(c);
}
return result.ToString();
}
static void Main() {
string s = "aabaa";
Console.WriteLine(MakeFancy(s));
}
}In Python, this implementation appends each character to a list and joins the list into a string at the end. It checks the last two characters of the list to determine if the current character can be appended.
Time Complexity: O(n). Space Complexity: O(n) due to the list storing characters incrementally.
Approach 2: Sliding Window Technique
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.
def make_fancy_string(s: str) -> str:
result = []
count = 1
for i in range(len(s)):
if i > 0 and s[i] == s[i - 1]:
count += 1
else:
count = 1
if count < 3:
result.append(s[i])
return ''.join(result)
s = "aabaa"
print(make_fancy_string(s))public class MakeFancyString {
public static String makeFancyString(String s) {
StringBuilder result = new StringBuilder();
int count = 1;
for (int i = 0; i < s.length(); i++) {
if (i > 0 && s.charAt(i) == s.charAt(i - 1)) {
count++;
} else {
count = 1;
}
if (count < 3) {
result.append(s.charAt(i));
}
}
return result.toString();
}
public static void main(String[] args) {
String s = "aabaa";
System.out.println(makeFancyString(s));
}
}#include <iostream>
#include <string>
std::string makeFancyString(const std::string& s) {
std::string result;
int count = 1;
for (size_t i = 0; i < s.length(); ++i) {
if (i > 0 && s[i] == s[i - 1]) {
count++;
} else {
count = 1;
}
if (count < 3) {
result += s[i];
}
}
return result;
}
int main() {
std::string s = "aabaa";
std::cout << makeFancyString(s) << std::endl;
return 0;
}function makeFancyString(s) {
let result = [];
let count = 1;
for (let i = 0; i < s.length; i++) {
if (i > 0 && s[i] === s[i - 1]) {
count++;
} else {
count = 1;
}
if (count < 3) {
result.push(s[i]);
}
}
return result.join('');
}
let s = "aabaa";
console.log(makeFancyString(s));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* makeFancyString(char* s) {
size_t len = strlen(s);
char* result = (char*)malloc(len + 1);
int index = 0, count = 1;
for (int i = 0; i < len; i++) {
if (i > 0 && s[i] == s[i - 1]) {
count++;
} else {
count = 1;
}
if (count < 3) {
result[index++] = s[i];
}
}
result[index] = '\0';
return result;
}
int main() {
char s[] = "aabaa";
char* result = makeFancyString(s);
printf("%s", result);
free(result);
return 0;
}using System;
using System.Text;
class MakeFancyString {
static string MakeFancy(string s) {
StringBuilder result = new StringBuilder();
int count = 1;
for (int i = 0; i < s.Length; i++) {
if (i > 0 && s[i] == s[i - 1]) {
count++;
} else {
count = 1;
}
if (count < 3) {
result.Append(s[i]);
}
}
return result.ToString();
}
static void Main() {
string s = "aabaa";
Console.WriteLine(MakeFancy(s));
}
}This Python implementation maintains a count of consecutive characters to determine if characters should be added to the result list, which is ultimately joined into a string.
Time Complexity: O(n). Space Complexity: O(n).
Approach 3: Simulation
We can iterate through the string s and use an array ans to record the current answer. For each character 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 ans.
Finally, we concatenate the characters in ans to get the answer.
The time complexity is O(n), where n is the length of the string s. Ignoring the space consumption of the answer, the space complexity is O(1).
function makeFancyString(s: string): string {
const ans: string[] = [];
for (let i = 0; i < s.length; ++i) {
if (s[i] !== s[i - 1] || s[i] !== s[i - 2]) {
ans.push(s[i]);
}
}
return ans.join('');
}func makeFancyString(s string) string {
ans := []byte{}
for i, ch := range s {
if c := byte(ch); i < 2 || c != s[i-1] || c != s[i-2] {
ans = append(ans, c)
}
}
return string(ans)
}class Solution {
/**
* @param String $s
* @return String
*/
function makeFancyString($s) {
$ans = '';
for ($i = 0; $i < strlen($s); $i++) {
$c = $s[$i];
if ($i < 2 || $c !== $s[$i - 1] || $c !== $s[$i - 2]) {
$ans .= $c;
}
}
return $ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simple Iterative Check | Time Complexity: |
| Sliding Window Technique | Time Complexity: |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Iterative Check | O(n) | O(n) | Best general solution. Clean logic and minimal checks when building the result string. |
| Sliding Window Technique | O(n) | O(n) | Useful when framing the problem as controlling a window of repeating characters. |
Frequently asked questions
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.