Delete Characters to Make Fancy String - Practice Coding Problems

Delete Characters to Make Fancy String - Problem

String Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "leeetcode"

› Output: "leetcode"

💡 Note: Remove one 'e' from the three consecutive 'e's. The result is "leetcode" with no three consecutive characters equal.

Example 2 — Multiple Groups

$ Input: s = "aaabaaaa"

› Output: "aabaa"

💡 Note: Remove one 'a' from "aaa" at start and two 'a's from "aaaa" at end. Result: "aabaa".

Example 3 — Already Fancy

$ Input: s = "aab"

› Output: "aab"

💡 Note: No three consecutive characters are equal, so no deletion needed.

Constraints

1 ≤ s.length ≤ 10⁵
s consists only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Original string with potential consecutive characters

Process

Remove minimum characters to avoid 3+ consecutive

Output

Fancy string with at most 2 consecutive characters

Key Takeaway

🎯 Key Insight: Only need to track the last 2 characters to prevent 3 consecutive duplicates

Asked in

a Amazon 15 M Microsoft 12

The key insight is to process the string character by character, keeping track of the last two characters added to the result. When we encounter a character that would create three consecutive identical characters, we simply skip it. The optimal approach uses a single pass with O(n) time and O(n) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Stack-like Approach	O(n)	O(n)	Use array/list as stack to build result efficiently
Brute Force Character by Character	O(n)	O(n)	Build result string by checking each character against previous two

Stack-like Approach — Algorithm Steps

Initialize result as list/array
For each character, check if it would form 3 consecutive with last 2 elements
Append character only if it doesn't violate the fancy string rule

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Stack Top

Look at last 2 elements in result array

Push or Skip

Add character if valid, skip if creates 3 consecutive

Join Result

Convert final array to string

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* s) {
    int len = strlen(s);
    char* result = (char*)malloc((len + 1) * sizeof(char));
    int pos = 0;
    
    for (int i = 0; i < len; i++) {
        if (pos >= 2 && result[pos - 1] == s[i] && result[pos - 2] == s[i]) {
            continue;
        }
        result[pos++] = s[i];
    }
    result[pos] = '\0';
    return result;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string with O(1) operations per character

✓ Linear Growth

Space Complexity

O(n)

Result array stores up to n characters

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-like Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler