Equal Character Frequencies After Removal

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

Given a string consisting of lowercase English letters, determine if it is possible to remove exactly one character so that the frequency of each remaining character is the same. Return true if such a removal is possible, otherwise false.

Examples:

Input: 'yummy'

Output: true

Explanation: After removing 'u', the string becomes 'yymm' with frequencies: y:2, m:2, which are the same.

Input: 'stop'

Output: true

Explanation: All characters initially have frequency 1. After removing any one character, the remaining characters still have frequency 1.

Input: 'aabb'

Output: false

Explanation: Frequencies are a:2, b:2. Removing any one character results in frequencies a:2,b:1 or a:1,b:2, which are not the same.

Constraints

2 <= length of string <= 1000
String contains only lowercase English letters.

Editorial

Intuition:

We need to determine if removing exactly one character can make all remaining character frequencies equal. The key insight is analyzing the frequency distribution: valid cases occur when (a) the string has only one distinct character, (b) all characters initially have frequency 1, or (c) there are exactly two distinct frequencies where one is 1 and occurs only once (remove that character) or one frequency is exactly one more than the other and occurs only once (remove one occurrence from that character).

Approach:

Count the frequency of each character in the string.
Build a frequency map that counts how many characters have each frequency.
Let distinctCharCount be the number of distinct characters.
If distinctCharCount is 1, return true (only one character type, removal leaves uniform frequency).
If there is only one distinct frequency value:
- If that frequency is 1, return true (all characters appear once, removal leaves others with frequency 1).
- Otherwise, return false (removing one creates two frequencies).
If there are exactly two distinct frequencies, let them be f1 (smaller) and f2 (larger):
- If f1 is 1 and exactly one character has frequency 1, return true (remove that character).
- If f2 equals f1+1 and exactly one character has frequency f2, return true (remove one occurrence from that character).
- Otherwise, return false.
If there are more than two distinct frequencies, return false (cannot fix by removing one character).

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool canMakeEqualFrequencies(string s) {
        unordered_map<char, int> charFreq;
        for (char c : s) {
            charFreq[c]++;
        }
        unordered_map<int, int> freqCount;
        for (auto& p : charFreq) {
            freqCount[p.second]++;
        }
        int distinctCharCount = charFreq.size();
        if (distinctCharCount == 1) return true;
        if (freqCount.size() == 1) {
            int f = freqCount.begin()->first;
            if (f == 1) return true;
            else return false;
        }
        if (freqCount.size() == 2) {
            vector<int> freqs;
            for (auto& p : freqCount) {
                freqs.push_back(p.first);
            }
            sort(freqs.begin(), freqs.end());
            int f1 = freqs[0], f2 = freqs[1];
            if ((f1 == 1 && freqCount[f1] == 1) || (f2 == f1 + 1 && freqCount[f2] == 1)) {
                return true;
            }
            return false;
        }
        return false;
    }
};
import java.util.*;

class Solution {
    public boolean canMakeEqualFrequencies(String s) {
        Map<Character, Integer> charFreq = new HashMap<>();
        for (char c : s.toCharArray()) {
            charFreq.put(c, charFreq.getOrDefault(c, 0) + 1);
        }
        Map<Integer, Integer> freqCount = new HashMap<>();
        for (int f : charFreq.values()) {
            freqCount.put(f, freqCount.getOrDefault(f, 0) + 1);
        }
        int distinctCharCount = charFreq.size();
        if (distinctCharCount == 1) return true;
        if (freqCount.size() == 1) {
            int f = freqCount.keySet().iterator().next();
            if (f == 1) return true;
            else return false;
        }
        if (freqCount.size() == 2) {
            List<Integer> freqs = new ArrayList<>(freqCount.keySet());
            Collections.sort(freqs);
            int f1 = freqs.get(0), f2 = freqs.get(1);
            if ((f1 == 1 && freqCount.get(f1) == 1) || (f2 == f1 + 1 && freqCount.get(f2) == 1)) {
                return true;
            }
            return false;
        }
        return false;
    }
}
from collections import Counter

class Solution:
    def canMakeEqualFrequencies(self, s: str) -> bool:
        char_freq = Counter(s)
        freq_count = Counter(char_freq.values())
        distinct_char_count = len(char_freq)
        if distinct_char_count == 1:
            return True
        if len(freq_count) == 1:
            f = next(iter(freq_count))
            if f == 1:
                return True
            else:
                return False
        if len(freq_count) == 2:
            freqs = sorted(freq_count.keys())
            f1, f2 = freqs[0], freqs[1]
            if (f1 == 1 and freq_count[f1] == 1) or (f2 == f1 + 1 and freq_count[f2] == 1):
                return True
            return False
        return False
function canMakeEqualFrequencies(s) {
    const charFreq = {};
    for (const c of s) {
        charFreq[c] = (charFreq[c] || 0) + 1;
    }
    const freqCount = {};
    for (const f of Object.values(charFreq)) {
        freqCount[f] = (freqCount[f] || 0) + 1;
    }
    const distinctCharCount = Object.keys(charFreq).length;
    if (distinctCharCount === 1) return true;
    const freqKeys = Object.keys(freqCount).map(Number);
    if (freqKeys.length === 1) {
        const f = freqKeys[0];
        if (f === 1) return true;
        else return false;
    }
    if (freqKeys.length === 2) {
        freqKeys.sort((a, b) => a - b);
        const f1 = freqKeys[0], f2 = freqKeys[1];
        if ((f1 === 1 && freqCount[f1] === 1) || (f2 === f1 + 1 && freqCount[f2] === 1)) {
            return true;
        }
        return false;
    }
    return false;
}

Complexity Analysis:

Time Complexity: O(n), where n is the length of the string. We traverse the string once to count frequencies and then process a constant number of distinct characters (at most 26).

Space Complexity: O(1) because we use two hash maps with at most 26 entries each (bounded by the alphabet size).

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories