Check if frequencies can be equal

JavaView on GFG

Time: O(n)

Space: O(1)

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?