1957. Delete Characters to Make Fancy String

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.

Approach 01:

class Solution {
 public:
  string makeFancyString(string inputString) {
    string resultString;
    
    for (const char currentChar : inputString) {
      // Append the character if the last two characters are not the same as the current one
      if (resultString.length() < 2 || resultString.back() != currentChar || resultString[resultString.size() - 2] != currentChar) {
        resultString.push_back(currentChar);
      }
    }
    
    return resultString;
  }
};

class Solution:
    def makeFancyString(self, inputString):
        resultString = ""
        
        for currentChar in inputString:
            # Append the character if the last two characters are not the same as the current one
            if len(resultString) < 2 or resultString[-1] != currentChar or resultString[-2] != currentChar:
                resultString += currentChar
        
        return resultString

Time Complexity

• Loop through Input String:

  The function iterates through each character in inputString once, performing constant-time operations for each character. Let \( N \) be the length of inputString. This results in a time complexity of \( O(N) \).

• Overall Time Complexity:

  The time complexity is \( O(N) \).

Space Complexity

• Result String:

  The output string resultString can hold up to \( N \) characters if no character repeats consecutively more than twice. Hence, the space complexity for storing resultString is \( O(N) \).

• Overall Space Complexity:

  The total space complexity is \( O(N) \), as the only additional storage used is resultString.