Delete Characters to Make Fancy String

Medium
1034.

Delete Characters to Make Fancy String

Delete Characters to Make Fancy String is a medium coding problem on strings and greedy, asked in Amazon, Google and TCS interviews.

A string is fancy if no three consecutive characters are equal.

Delete the minimum number of characters from s to make it fancy and return the result. The answer is unique.

Example 1

Input
s = "cooodekairo"
Output
coodekairo
Explanation
One `o` is dropped from the run of three.

Example 2

Input
s = "aaabaaaa"
Output
aabaa
Explanation
Each run longer than two is trimmed to two.

Example 3

Input
s = "aab"
Output
aab
Explanation
Already fancy.

Constraints

  • 1 <= s.length <= 10^5
  • s consists only of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var makeFancyString = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Delete Characters to Make Fancy String — Problem & Solution

Delete Characters to Make Fancy String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Delete Characters to Make Fancy String is a medium coding problem on strings and greedy, asked in Amazon, Google and TCS interviews.

  • Difficulty: Medium
  • Topics: Strings, Greedy
  • Asked at: Amazon, Google, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A string is fancy if no three consecutive characters are equal.

Delete the minimum number of characters from s to make it fancy and return the result. The answer is unique.

Example 1

Input: s = "cooodekairo"
Output: coodekairo
Explanation: One `o` is dropped from the run of three.

Example 2

Input: s = "aaabaaaa"
Output: aabaa
Explanation: Each run longer than two is trimmed to two.

Example 3

Input: s = "aab"
Output: aab
Explanation: Already fancy.

Constraints

  • 1 <= s.length <= 10^5
  • s consists only of lowercase English letters.

Hints for Delete Characters to Make Fancy String

  1. Hint 1

    Build the answer left to right and only look at the last two characters you kept.

  2. Hint 2

    Skip the incoming character if those two already equal it.

  3. Hint 3

    Equivalently, keep the first two characters of every run and drop the rest.

How to solve Delete Characters to Make Fancy String

Build the result greedily: append each character unless the last two already appended are equal to it. That keeps exactly the first two characters of every run.

Approach

  1. Start with an empty output.
  2. For each character of s, skip it if the output's last two characters both equal it.
  3. Otherwise append it.

Why it works

Deleting from the end of a run rather than the start costs the same and keeps the check local — only the last two kept characters ever matter, so no lookahead or run-boundary bookkeeping is needed. The answer is unique because within a run every character is identical, so which copies are removed is irrelevant; only how many.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • Compare against the output being built, not against the original string — deletions shift the context.
  • Runs of exactly two are legal and must be kept intact.
  • Deleting the whole run is wrong; two copies survive.

Reference solution

Python

def makeFancyString(s: str) -> str:
    out = []
    for c in s:
        if len(out) >= 2 and out[-1] == c and out[-2] == c:
            continue
        out.append(c)
    return "".join(out)

Java

public static String makeFancyString(String s) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        int n = sb.length();
        if (n >= 2 && sb.charAt(n - 1) == c && sb.charAt(n - 2) == c) continue;
        sb.append(c);
    }
    return sb.toString();
}

C++

string makeFancyString(string s) {
    string out;
    for (char c : s) {
        size_t n = out.size();
        if (n >= 2 && out[n - 1] == c && out[n - 2] == c) continue;
        out += c;
    }
    return out;
}

JavaScript

var makeFancyString = function(s) {
    var out = "";
    for (var i = 0; i < s.length; i++) {
        var n = out.length;
        var c = s.charAt(i);
        if (n >= 2 && out.charAt(n - 1) === c && out.charAt(n - 2) === c) continue;
        out += c;
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms