Katkat
Back

Check equal character frequencies

BloombergSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use frequency mapping to determine if a string can be transformed into a state where all characters appear the same number of times through a single character removal.

Problem Statement

Given a string s, determine if it is possible to make all characters in the string appear the same number of times by removing exactly one character.

Return true if it is possible, and false otherwise.

Constraints

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.

Examples

Example 1: Input: s = "abcc" Output: true Explanation: Removing one 'c' leaves 'a', 'b', 'c', each appearing once.

Example 2: Input: s = "aabbcccd" Output: false Explanation: Removing one character cannot equalize frequencies.

Edge Cases

  • A string of length 1 should return true (removing the character leaves an empty string, which satisfies the condition).
  • A string where all characters already have the same frequency, but removing one makes the counts unequal.
  • A string with two characters like "aabb".

Hints

Hint 1

First, calculate the frequency of every character using a hash map or an array of size 26.

Hint 2

Once you have the counts, consider how the frequencies of those counts (e.g., 'three characters appear twice') affect the possibility of equalization.

Hint 3

Think about the cases where removal is successful: either all characters appear once, or there is exactly one character that appears one more time than all other characters (which appear with the same frequency).

Follow-up questions

  • How would your approach change if you were allowed to remove at most one character instead of exactly one?
  • What is the time and space complexity of your solution, and can it be optimized if the alphabet size is fixed?
  • How would you handle the requirement if the input string contained Unicode characters rather than just lowercase English letters?