# Delete Characters to Make Fancy String
**Difficulty:** EASY
[External](https://leetcode.com/problems/delete-characters-to-make-fancy-string)
Canonical: https://scaleengineer.com/dsa/problems/delete-characters-to-make-fancy-string
**Data structures:** String
**Companies:** [Wayfair](https://scaleengineer.com/companies/wayfair)
---
## 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 <= 105`
* `s` consists only of lowercase English letters.

# Approaches
## Brute Force with String Concatenation
This approach iterates through the input string and builds a new result string. For each character, it decides whether to append it to the result by checking the last two characters of the currently built string. It uses standard string concatenation, which is inefficient in Java because strings are immutable.
**Time:** O(N^2), where N is the length of the string `s`. In Java, strings are immutable. The operation `result += c` creates a new `StringBuilder`, appends the characters, and then creates a new `String`. In a loop, this repeated creation and copying leads to quadratic time complexity. · **Space:** O(N), where N is the length of the string. Although many intermediate strings are created (leading to O(N^2) total allocations), the space required at any single point for the `result` string is at most O(N).
**Pros:** Simple to understand and implement the logic.
**Cons:** Very inefficient due to repeated string concatenation in a loop.; Will likely result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints.
### Explanation
We initialize an empty string, let's call it `result`. We loop through each character `c` of the input string `s`. In each iteration, we check the length of `result`. If the length is less than 2, we can safely append `c`. If the length is 2 or more, we check if the last character `result.charAt(result.length() - 1)` and the second to last character `result.charAt(result.length() - 2)` are both equal to the current character `c`. If they are not both equal to `c`, we append `c` to `result` using the `+` operator. This process continues until all characters in `s` are processed. The main drawback is that string concatenation `result = result + c` in a loop creates a new string object in each step, leading to poor performance.

```java
class Solution {
    public String makeFancyString(String s) {
        if (s.length() < 3) {
            return s;
        }
        String result = "";
        result += s.charAt(0);
        result += s.charAt(1);
        for (int i = 2; i < s.length(); i++) {
            char c = s.charAt(i);
            int len = result.length();
            if (c != result.charAt(len - 1) || c != result.charAt(len - 2)) {
                result += c;
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty string `result`.
- Iterate through the input string `s` from left to right.
- For each character `c`, get the current length of `result`.
- If `result.length()` is less than 2, append `c` to `result` using the `+` operator.
- Otherwise, if `c` is not equal to the last character of `result` or `c` is not equal to the second-to-last character of `result`, append `c` to `result`.
- After iterating through all characters, return `result`.

## Using StringBuilder
A more efficient approach that uses a `StringBuilder` to construct the result string. `StringBuilder` is mutable, so appending characters is much faster than using string concatenation, leading to a linear time complexity.
**Time:** O(N), where N is the length of the string `s`. We iterate through the string once, and each append operation on the `StringBuilder` takes amortized constant time. · **Space:** O(N), where N is the length of the string `s`. The `StringBuilder` can grow up to the size of the input string, requiring O(N) space for its internal character array.
**Pros:** Efficient O(N) time complexity.; Idiomatic Java for string manipulation in loops.; Easy to read and maintain.
**Cons:** Uses O(N) extra space for the `StringBuilder`.
### Explanation
This method follows the same logic as the brute-force approach but replaces the inefficient string concatenation with a `StringBuilder`. We initialize an empty `StringBuilder`. We iterate through the input string `s`. For each character, we check if it can be appended without creating three consecutive identical characters. The condition is the same: the `StringBuilder`'s length is less than 2, or the new character is not identical to the last two characters already in the `StringBuilder`. If the condition holds, we append the character using `StringBuilder.append()`, which is an amortized O(1) operation. Finally, we convert the `StringBuilder` to a string and return it. This is the standard and recommended way to build strings in a loop in Java.

```java
class Solution {
    public String makeFancyString(String s) {
        if (s.length() < 3) {
            return s;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int len = sb.length();
            if (len < 2 || c != sb.charAt(len - 1) || c != sb.charAt(len - 2)) {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}
```
### Algorithm
- Initialize an empty `StringBuilder sb`.
- Iterate through the input string `s` from left to right.
- For each character `c`, get the current length of `sb`.
- If `sb.length()` is less than 2, append `c` to `sb`.
- Otherwise, if `c` is not equal to `sb.charAt(sb.length() - 1)` or `c` is not equal to `sb.charAt(sb.length() - 2)`, append `c` to `sb`.
- After the loop, convert `sb` to a string and return it.

## Two Pointers (In-place Style)
This approach uses a two-pointer technique to build the result string in a character array. It's a space-optimized variant of the `StringBuilder` approach, often with better performance due to direct array manipulation and avoiding `StringBuilder` overhead. This is a classic pattern for filtering an array or string.
**Time:** O(N), where N is the length of the string `s`. We iterate through the character array once. Converting the string to a character array and creating the final string from the array both take O(N) time. · **Space:** O(N). We create a character array of size N to work with. The final returned string also takes O(N) space. While this is an 'in-place style' algorithm, in Java, it still requires O(N) space due to string immutability. The benefit is mainly in performance constant factors.
**Pros:** Highly efficient, often faster in practice than `StringBuilder` due to direct memory access and avoiding object overhead.; A common and useful pattern for array/string filtering problems.; Optimal time complexity.
**Cons:** The logic can be slightly more complex to reason about than the straightforward `StringBuilder` approach.
### Explanation
This method simulates an in-place modification. We convert the input string to a character array. We use two pointers: a read pointer `i` that scans the original array, and a write pointer `j` that indicates the end of the valid 'fancy' string being built. The first two characters of the string are always part of the fancy string (if they exist), so we can initialize our result with them and start our pointers `i` and `j` from 2. We iterate with `i` from 2 to the end of the character array. For each character `chars[i]`, we compare it with the last two characters of our valid prefix, which are at `chars[j-1]` and `chars[j-2]`. If `chars[i]` is not equal to both `chars[j-1]` and `chars[j-2]`, it means we can keep this character. We place it at the `j`-th position (`chars[j] = chars[i]`) and advance the write pointer (`j++`). If `chars[i]` is the same as the previous two characters, we simply skip it by advancing `i` without changing `j`. After the loop, the fancy string is the prefix of the character array of length `j`. We create a new string from this prefix and return it.

```java
class Solution {
    public String makeFancyString(String s) {
        int n = s.length();
        if (n < 3) {
            return s;
        }
        char[] chars = s.toCharArray();
        int j = 2; // j is the write pointer, points to the next available spot
        for (int i = 2; i < n; i++) { // i is the read pointer
            // We can keep the character if it's not the same as the previous two.
            if (chars[i] != chars[j - 1] || chars[i] != chars[j - 2]) {
                chars[j] = chars[i];
                j++;
            }
        }
        return new String(chars, 0, j);
    }
}
```
### Algorithm
- Handle the base case: if the string length is less than 3, return the string itself.
- Convert the input string `s` into a character array `chars`.
- Initialize a write pointer `j = 2`. The first two characters are always kept.
- Iterate with a read pointer `i` from 2 to `s.length() - 1`.
- Inside the loop, check if `chars[i]` is different from `chars[j-1]` or `chars[j-2]`.
- If the condition is true, it means the character can be kept. Copy the character: `chars[j] = chars[i]`, and then increment `j`.
- After the loop, create a new string from the `chars` array, using the characters from index 0 up to (but not including) `j`.
- Return the new string.

# Solutions
### Java

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

```

### JavaScript

```javascript
function makeFancyString ( s ) { let [ n , ans ] = [ s . length , '' ]; for ( let i = 0 ; i < n ; i ++ ) { if ( s [ i ] !== s [ i - 1 ] || s [ i ] !== s [ i - 2 ]) { ans += s [ i ]; } } return ans ; }
```

### CPP

```cpp
class Solution {
public:
  string makeFancyString(string s) {
    string ans = "";
    for (char &c : s) {
      int n = ans.size();
      if (n > 1 && ans[n - 1] == c && ans[n - 2] == c)
        continue;
      ans.push_back(c);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def makeFancyString(self, s: str) -> str: ans = [] for c in s: if len(ans) > 1 and ans[- 1] == ans[- 2] == c: continue ans . append(c) return '' . join(ans)

```