algoadvance

Leetcode 2423. Remove Letter To Equalize Frequency

Problem Statement

Given a string word, you have to remove exactly one character from the string so that the frequency of each character in the string becomes the same. Return true if it’s possible to achieve that, or false otherwise.

Example 1:

Input: word = "abcc"
Output: true
Explanation: Removing 'c' from "abcc" will make the frequency of 'a' and 'b' both 1.

Example 2:

Input: word = "aazz"
Output: false

Clarifying Questions

  1. What are the constraints on the length of the input string?
    • The string word will have a length in the range [2, 10^5].
  2. What characters does the string word contain?
    • The string contains only lowercase English letters (‘a’ to ‘z’).
  3. Is it necessary to remove exactly one character, or can we choose not to remove any at all?
    • You must remove exactly one character to achieve the equal frequency condition.
  4. Are there any edge cases to consider, such as an extremely short string?
    • Since the length range is [2, 10^5], the minimum length will be 2, so an empty string or a single-character string is not a concern.

Strategy

To solve this problem, follow these steps:

  1. Calculate the frequency of each character in the input string.
  2. Maintain a frequency counter for these frequencies.
  3. Check whether it’s possible to get either exactly one or two unique frequencies such that removing one character equalizes the frequency.

Here’s a more detailed breakdown:

  1. Count the frequency of each character.
  2. Use another count map to keep track of how many times each frequency appears.
  3. There are a few scenarios where removal of exactly one character can make all characters have the same frequency:
    • If there’s only one unique frequency (already balanced).
    • If there are two frequencies, one of them should be 1 and should appear exactly once. Removing a character with this frequency will balance the string.
    • If there are two frequencies, and their difference is exactly 1, removing any one character from the higher frequency group should balance the string.

Code

#include <iostream>
#include <unordered_map>
#include <string>
#include <cmath>

bool equalFrequency(std::string word) {
    std::unordered_map<char, int> charFreq;
    for (char c : word) {
        charFreq[c]++;
    }

    std::unordered_map<int, int> freqCount;
    for (auto& cf : charFreq) {
        freqCount[cf.second]++;
    }

    if (freqCount.size() == 1) {
        // All characters already have the same frequency or all except one
        return true;
    } else if (freqCount.size() == 2) {
        // There are exactly two different frequencies
        auto it1 = freqCount.begin();
        auto it2 = it1;
        ++it2;

        // Ensure that the first frequency is the smaller one
        if (it1->first > it2->first) {
            std::swap(it1, it2);
        }

        // Now it1 is the smaller frequency
        if (it1->first == 1 && it1->second == 1) {
            // Case where there's exactly one character with frequency 1
            return true;
        }
        
        if (it2->first == it1->first + 1 && it2->second == 1) {
            // Case where removing one character from the higher frequency
            return true;
        }
    }
  
    return false;
}

int main() {
    std::string word1 = "abcc";
    std::string word2 = "aazz";
    std::cout << std::boolalpha << equalFrequency(word1) << std::endl; // true
    std::cout << std::boolalpha << equalFrequency(word2) << std::endl; // false
    return 0;
}

Time Complexity

The time complexity of the solution is (O(n)), where (n) is the length of the input string.

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