Check if frequencies can be equal

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Check if all characters can have equal frequency by removing exactly one character occurrence.

Intuition

Check if all characters can have equal frequency by removing exactly one character occurrence.

Algorithm

1Count frequencies. If all equal: valid. If one frequency is 1 more than others and occurs once: remove it.
2Special cases: only one distinct char, or all same frequency, or (n-1)/k = uniform after one removal.

Common Pitfalls

• Multiple edge cases. Valid conditions: 1) all same freq, 2) removing one occurrence makes all equal, 3) one char with freq 1 can be fully removed.

Check if frequencies can be equal.java

Java

// Approach: Count character frequencies. Find if removing exactly one character can make all frequencies equal.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    boolean sameFreq(String s) {
        HashMap<Character, Integer> freqmap = new HashMap<>();
        for (char ch : s.toCharArray())
            freqmap.put(ch, freqmap.getOrDefault(ch, 0) + 1);// {a-3,b-3,c-2}

        HashMap<Integer, Integer> countmap = new HashMap<>();
        for (int freq : freqmap.values())
            countmap.put(freq, countmap.getOrDefault(freq, 0) + 1);// {3-2,2-1}

        if (countmap.size() == 1)
            return true;
        else if (countmap.size() > 2)
            return false;
        else {
            int freq1 = 0;
            int freq2 = 0;
            int value1 = 0;
            int value2 = 0;
            int i = 0;
            for (Map.Entry<Integer, Integer> entry : countmap.entrySet()) {
                if (i == 0) {
                    freq1 = entry.getKey();
                    value1 = entry.getValue();
                } else {
                    freq2 = entry.getKey();
                    value2 = entry.getValue();
                }
                i++;
            }
            if ((freq1 == 1 && value1 == 1) || (freq2 == 1 && value2 == 1))
                return true;
        

            if ((Math.abs(freq1 - freq2) == 1) 
                && ((freq1 > freq2 && value1 == 1) || (freq2 > freq1 && value2 == 1)))
                return true;

            return false;

        }
    }
}

Was this solution helpful?