algoadvance

Leetcode 2423. Remove Letter To Equalize Frequency

Problem Statement

Given a string s, you are allowed to remove one character from the string. Your task is to determine if you can remove exactly one character so that the frequency of every distinct character in the string is the same.

Clarifying Questions

  1. Can the input string contain non-alphabetic characters?
    • Assume the string consists only of lowercase alphabetic characters.
  2. What should be the output if it’s not possible to equalize the frequency by removing one character?
    • Return false.
  3. What should be the output if it’s already possible to equalize the frequency without removing any character?
    • Return true.
  4. Can the length of the string be zero?
    • No, the string length will always be between 1 and 100,000.

Strategy

  1. Use a frequency counter to count the occurrences of each character in the string.
  2. Create a set to collect unique frequencies.

  3. Depending on the number of unique frequencies, check the conditions under which a single deletion might equalize them.

    Cases to Consider:

    • If all characters already have the same frequency, return true.
    • If there are exactly two unique frequencies:
      • One frequency must be 1; and the letter frequency with just one occurrence should be reduced to 0 upon removal.
      • The difference between the two frequencies must be 1, indicating that removing one instance of the higher frequency character will make the two frequencies equal.

Code

import java.util.HashMap;
import java.util.HashSet;

public class Solution {
    public boolean equalFrequency(String s) {
        // Step 1: Calculate character frequencies
        HashMap<Character, Integer> frequencyMap = new HashMap<>();
        
        for (char c : s.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }

        // Step 2: Calculate frequencies of those frequencies
        HashMap<Integer, Integer> freqCountMap = new HashMap<>();
        for (int freq : frequencyMap.values()) {
            freqCountMap.put(freq, freqCountMap.getOrDefault(freq, 0) + 1);
        }

        // Step 3: Analyze the frequency counts
        if (freqCountMap.size() == 1) {
            // All characters have the same frequency
            return true;
        } else if (freqCountMap.size() == 2) {
            // Two distinct frequencies
            int[] keys = new int[2];
            int[] values = new int[2];
            int i = 0;

            for (int key : freqCountMap.keySet()) {
                keys[i] = key;
                values[i] = freqCountMap.get(key);
                i++;
            }

            int freq1 = keys[0], count1 = values[0];
            int freq2 = keys[1], count2 = values[1];

            // Case 1: One frequency is 1 and its count is 1
            if ((freq1 == 1 && count1 == 1) || (freq2 == 1 && count2 == 1)) {
                return true;
            }

            // Case 2: Difference between frequencies is 1 and higher frequency count is 1
            if ((freq1 == freq2 + 1 && count1 == 1) || (freq2 == freq1 + 1 && count2 == 1)) {
                return true;
            }
        }

        // In all other cases, it's not possible to equalize the frequencies by removing one letter
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.equalFrequency("abcc")); // Output: true
        System.out.println(sol.equalFrequency("aazz")); // Output: false
    }
}

Time Complexity

In this approach, the most time-consuming part is traversing the string to compute frequencies, which is linear relative to the size of the string. Hence, the solution is efficient for the given constraint (1 ≤ s.length ≤ 100,000).

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