Solution Explanation for 1957. Delete Characters to Make Fancy String

This problem asks us to modify a given string s such that no three consecutive characters are identical. The goal is to achieve this by removing the minimum number of characters.

Approach: Iterative Construction

The most efficient approach is to iteratively build a new string (ans), adding characters from the input string s only if they don't violate the "fancy string" condition.

We maintain a check on the last two characters added to ans. If the current character from s is the same as the last two, we skip it; otherwise, we append it to ans.

Algorithm

1. Initialization: Create an empty string ans to store the result.

2. Iteration: Iterate through each character c in the input string s.

3. Conditional Appending:

   • If ans has fewer than 2 characters, or if the last character of ans is different from c, or if the second-to-last character of ans is different from c, then append c to ans.

4. Return: After processing all characters, return ans.

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the length of the input string s. We iterate through the string once.
• Space Complexity: O(n) in the worst case. In the worst case, we might need to store a string of length n (although on average it will likely use less space).

Code Implementation in various languages

Python

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

Java

class Solution {
    public String makeFancyString(String s) {
        StringBuilder ans = new StringBuilder();
        for (char c : s.toCharArray()) {
            int n = ans.length();
            if (n < 2 || ans.charAt(n - 1) != c || (n >= 2 && ans.charAt(n - 2) != c)) {
                ans.append(c);
            }
        }
        return ans.toString();
    }
}

C++

class Solution {
public:
    string makeFancyString(string s) {
        string ans = "";
        for (char c : s) {
            if (ans.length() < 2 || ans.back() != c || ans.length() >= 2 && ans[ans.length() - 2] != c) {
                ans += c;
            }
        }
        return ans;
    }
};

JavaScript

var makeFancyString = function(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]) {
            result += s[i];
        }
    }
    return result;
};

Go

func makeFancyString(s string) string {
	ans := []rune{}
	for _, r := range s {
		if len(ans) < 2 || ans[len(ans)-1] != r || (len(ans) >= 2 && ans[len(ans)-2] != r) {
			ans = append(ans, r)
		}
	}
	return string(ans)
}

These implementations all follow the same basic algorithm, demonstrating its simplicity and efficiency across different programming languages. They all achieve a linear time complexity, making them suitable for handling large input strings.