algoadvance

Leetcode 1957. Delete Characters to Make Fancy String

Problem Statement

LeetCode Problem 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".

Clarifying Questions

  1. Is the string s guaranteed to be non-empty?
    • Yes, for this problem, we can assume the string is non-empty.
  2. What are the constraints on the length of the string s?
    • The length of s will be between 1 and 10^5, inclusive.
  3. What characters does the string s contain?
    • The string consists of lowercase English letters only.

Strategy

Steps:

  1. Initialize an empty result string or vector.
  2. Traverse the input string s character by character.
  3. For each character, check the last two characters of the result string.
  4. Only add the current character to the result string if adding it does not form a group of three consecutive same characters.

This ensures that the resulting string will be fancy.

Code

Here is the C++ implementation of the above strategy:

#include <iostream>
#include <string>
using namespace std;

string makeFancyString(string s) {
    string result;
    
    for (char c : s) {
        int n = result.size();
        // Ensure no three consecutive characters are equal
        if (n >= 2 && result[n-1] == c && result[n-2] == c) {
            continue;
        }
        result += c;
    }
    
    return result;
}

// Example Usage
int main() {
    string s1 = "leeetcode";
    cout << "Result for " << s1 << " : " << makeFancyString(s1) << endl;

    string s2 = "aaabaaaa";
    cout << "Result for " << s2 << " : " << makeFancyString(s2) << endl;

    string s3 = "aab";
    cout << "Result for " << s3 << " : " << makeFancyString(s3) << endl;

    return 0;
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string. This is because we traverse the string once, and each insertion into the result string happens in constant time.

The space complexity is O(n) because in the worst case, we store a copy of the input string without any deletions.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI