Scale Engineer

Remove Letter To Equalize Frequency

Easy
#2207Time: O(N^2), where N is the length of `word`. The outer loop runs N times. Inside the loop, creating the substring takes O(N) and checking its frequencies also takes O(N). Thus, the total time is N * (O(N) + O(N)) = O(N^2).Space: O(N), where N is the length of `word`. A temporary string of length N-1 is created in each iteration. The frequency array inside the helper function takes O(1) space as the alphabet size is constant.1 company
Patterns
Counting
Data structures
Hash TableString
Companies
tcs

Prompt

You are given a 0-indexed string word, consisting of lowercase English letters. You need to select one index and remove the letter at that index from word so that the frequency of every letter present in word is equal.

Return true if it is possible to remove one letter so that the frequency of all letters in word are equal, and false otherwise.

Note:

  • The frequency of a letter x is the number of times it occurs in the string.
  • You must remove exactly one letter and cannot choose to do nothing.

 

Example 1:

Input: word = "abcc"
Output: true
Explanation: Select index 3 and delete it: word becomes "abc" and each character has a frequency of 1.

Example 2:

Input: word = "aazz"
Output: false
Explanation: We must delete a character, so either the frequency of "a" is 1 and the frequency of "z" is 2, or vice versa. It is impossible to make all present letters have equal frequency.

 

Constraints:

  • 2 <= word.length <= 100
  • word consists of lowercase English letters only.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We iterate through every character in the input string word. For each character, we consider removing it and then check if the remaining characters in the modified string all have the same frequency. If we find any such removal that satisfies the condition, we can immediately return true. If we exhaust all possible single-character removals and none result in equal frequencies, we return false.

Algorithm

  • Iterate through each index i of the word from 0 to word.length() - 1.
  • For each i, create a new temporary string tempWord by removing the character at that index.
  • Check if all characters in tempWord have the same frequency using a helper function.
    • The helper function calculates character frequencies for tempWord.
    • It finds the frequency of the first character present in tempWord and sets it as targetFreq.
    • It then verifies that all other characters present in tempWord also have the frequency targetFreq.
  • If the helper function returns true, it means a valid removal has been found, so we return true from the main function.
  • If the loop completes without finding any such i, it means no single removal can satisfy the condition. Return false.

Walkthrough

The algorithm proceeds as follows:

  1. Loop through each index i from 0 to word.length() - 1. This represents selecting the character at index i to be removed.
  2. Inside the loop, construct a new temporary string by removing the character at index i. For example, if word is "abcc" and i is 2, the new string is "abc".
  3. Create a helper function, say areFrequenciesEqual(String s), that checks if all characters present in a string s have the same frequency.
    • This function first calculates the frequency of each character in s and stores them, for instance, in an array of size 26.
    • It then iterates through these frequencies. It finds the first non-zero frequency and stores it as the target frequency.
    • It continues iterating, and if it finds any other non-zero frequency that is different from the target frequency, it returns false.
    • If the loop completes without finding any mismatch, it means all present characters have the same frequency, so it returns true.
  4. Call this helper function on the temporary string. If it returns true, it means we've found a valid removal. We can stop and return true from the main function.
  5. If the loop completes without finding any valid removal, it means it's impossible. We return false.
class Solution {    public boolean equalFrequency(String word) {        for (int i = 0; i < word.length(); i++) {            // Create a new string with one character removed.            StringBuilder sb = new StringBuilder(word);            sb.deleteCharAt(i);            String tempWord = sb.toString();                        if (areFrequenciesEqual(tempWord)) {                return true;            }        }        return false;    }     private boolean areFrequenciesEqual(String s) {        if (s.isEmpty()) {            return true;        }                int[] freq = new int[26];        for (char c : s.toCharArray()) {            freq[c - 'a']++;        }                int targetFreq = 0;        // Find the frequency of the first character present.        for (int count : freq) {            if (count > 0) {                targetFreq = count;                break;            }        }                // Check if all other present characters have the same frequency.        for (int count : freq) {            if (count > 0 && count != targetFreq) {                return false;            }        }                return true;    }}

Complexity

Time

O(N^2), where N is the length of `word`. The outer loop runs N times. Inside the loop, creating the substring takes O(N) and checking its frequencies also takes O(N). Thus, the total time is N * (O(N) + O(N)) = O(N^2).

Space

O(N), where N is the length of `word`. A temporary string of length N-1 is created in each iteration. The frequency array inside the helper function takes O(1) space as the alphabet size is constant.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the logic of the problem statement, making it intuitive.

Cons

  • Inefficient due to its quadratic time complexity.

  • Involves repeated computations, as frequencies are recalculated for each modified string.

  • Creates many temporary string objects, which can be memory-intensive for very long strings (though not an issue with the given constraints).

Solutions

class Solution {public  boolean equalFrequency(String word) {    int[] cnt = new int[26];    for (int i = 0; i < word.length(); ++i) {      ++cnt[word.charAt(i) - 'a'];    }    for (int i = 0; i < 26; ++i) {      if (cnt[i] > 0) {        --cnt[i];        int x = 0;        boolean ok = true;        for (int v : cnt) {          if (v == 0) {            continue;          }          if (x > 0 && v != x) {            ok = false;            break;          }          x = v;        }        if (ok) {          return true;        }        ++cnt[i];      }    }    return false;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem