• Leetcode POTDs

Problem 1957 Delete Characters to Make Fancy String

Problem Statement

Link - Problem 1957

Question

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.

Solution

class Solution {
public:
    string makeFancyString(string& s) {
        for (int i = 2; i < s.size(); i++) {
            if (s[i] == s[i - 1] && s[i] == s[i - 2]) {
                s.erase(i, 1);
                i--;
            }
        }
        return s;
    }
};

Complexity Analysis

| Algorithm                                         | Time Complexity | Space Complexity |
| ------------------------------------------------- | --------------- | ---------------- |
| Single pointer traversal with string modification | O(n)            | O(1)             |

Explanation

1. Intuition

• The problem requires deleting the minimum number of characters from a string to make it fancy, where no three consecutive characters are equal.
• A greedy approach can be used to solve this problem, where we delete characters as soon as we find three consecutive equal characters.
• This approach works because deleting a character will not affect the decision to delete or not delete the next character.
• The problem can be solved in a single pass through the string, making it efficient for large inputs.
• The solution does not require any additional data structures, making it space-efficient.
• The time complexity of the solution is O(n), where n is the length of the string.
• The solution is also unique, as the problem statement guarantees that the answer will always be unique.

2. Implementation

• The solution starts by iterating through the string from the third character to the end, using a for loop: for (int i = 2; i < s.size(); i++).
• Inside the loop, it checks if the current character is equal to the previous two characters, using the condition if (s[i] == s[i - 1] && s[i] == s[i - 2]).
• If the condition is true, it deletes the current character from the string using the erase method: s.erase(i, 1).
• After deleting the character, it decrements the loop counter to account for the deleted character: i--.
• The loop continues until the end of the string is reached, at which point the function returns the modified string.
• The erase method is used to delete the character, which modifies the string in-place.
• The solution uses a single loop and does not require any additional data structures, making it efficient.

Complexity Analysis

Time Complexity:

• The algorithm traverses the string once, with a single loop that runs from the third character to the end of the string, resulting in a linear time complexity.
• The dominant operations are the string comparison at s[i] == s[i - 1] && s[i] == s[i - 2] and the string erase at s.erase(i, 1). Both are constant time or linear with respect to the size of the remaining string, contributing to an overall linear time complexity.
• The time complexity is O(n) because the algorithm performs a constant amount of work for each character in the input string, where n is the size of the input string.

Space Complexity:

• The algorithm modifies the input string in-place, which means it does not use any additional space proportional to the input size.
• There is no use of data structures such as arrays or linked lists that grow with the size of the input.
• The space complexity is O(1) because the algorithm uses a constant amount of space to store variables such as the loop counter i, regardless of the input size.

Footnote

This question is rated as Easy difficulty.

Hints

What’s the optimal way to delete characters if three or more consecutive characters are equal?

If three or more consecutive characters are equal, keep two of them and delete the rest.

Similar Questions: