# Remove Letter To Equalize Frequency
**Difficulty:** EASY
[External](https://leetcode.com/problems/remove-letter-to-equalize-frequency)
Canonical: https://scaleengineer.com/dsa/problems/remove-letter-to-equalize-frequency
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [tcs](https://scaleengineer.com/companies/tcs)
---
## Problem
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
## Brute-Force Simulation
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`.
**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.
**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).
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Frequency Analysis
Instead of simulating each removal, we can analyze the frequencies of characters in the original string. A valid removal is possible only if the character frequencies follow a specific pattern. By counting the frequencies of characters and then analyzing the distribution of these frequency counts, we can determine the answer in a single pass over the string.
**Time:** O(N), where N is the length of `word`. We iterate through the word once to build the frequency map (O(N)). Then we iterate through the frequency map (O(1), size 26) and the count map (O(1), max size 2 for a valid case). The overall complexity is dominated by the initial pass over the string. · **Space:** O(1). The `freq` array has a constant size of 26. The `countMap` will also have a very small size (at most 26), so it's considered constant space.
**Pros:** Highly efficient with linear time complexity.; Constant space complexity, as the storage used does not depend on the input size.; Avoids string manipulation and repeated computations.
**Cons:** The logic is more complex and less intuitive than the brute-force approach.; It requires careful case analysis of the frequency distributions, which can be tricky to get right.
### Explanation
The core idea is that after removing one character, all remaining characters must have the same frequency, say `k`. This places strong constraints on the original frequency distribution. Let's analyze the map of frequencies (how many characters have a certain frequency).

1.  First, calculate the frequency of each character in the `word`. We can use an array `freq` of size 26 for this.
2.  Next, create a map `countMap` to store the frequency of frequencies. For example, if `word` is "abcc", the character frequencies are `a:1, b:1, c:2`. The `countMap` would be `{1:2, 2:1}` because two characters have a frequency of 1, and one character has a frequency of 2.
3.  The number of distinct frequencies in the original string (i.e., `countMap.size()`) can be at most 2 for a solution to be possible. If it's greater than 2, we can immediately return `false`.
4.  We then analyze the `countMap` based on its size:
    *   **Case 1: `countMap.size() == 1`**
        *   This means all characters have the same frequency, `f`. If we remove one character, its frequency becomes `f-1`. For the new frequencies to be equal, either the original frequency `f` must be 1 (e.g., "abc" -> "ab"), or there's only one distinct character to begin with (e.g., "aaaa" -> "aaa").
    *   **Case 2: `countMap.size() == 2`**
        *   Let the two frequencies be `f1`, `f2` with counts `c1`, `c2`. A solution exists in two scenarios:
            *   **Scenario A:** We remove a character that has a frequency of 1, and it's the only character with that frequency. This removes the character and its frequency group entirely, leaving a single group where all characters have the same frequency (e.g., in "abbcc", removing 'a' leaves "bbcc").
            *   **Scenario B:** We reduce a character's frequency to match the other frequency group. This is only possible if the higher frequency is just one greater than the lower frequency, and there's only one character with that higher frequency (e.g., in "abcc", removing 'c' (freq 2) makes its frequency 1, matching 'a' and 'b').
5.  If none of these conditions are met, it's impossible, so we return `false`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean equalFrequency(String word) {
        int[] freq = new int[26];
        for (char c : word.toCharArray()) {
            freq[c - 'a']++;
        }

        Map<Integer, Integer> countMap = new HashMap<>();
        for (int f : freq) {
            if (f > 0) {
                countMap.put(f, countMap.getOrDefault(f, 0) + 1);
            }
        }

        if (countMap.size() > 2) {
            return false;
        }

        if (countMap.size() == 1) {
            for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
                int f = entry.getKey();
                int c = entry.getValue();
                if (f == 1 || c == 1) {
                    return true;
                }
            }
            return false;
        }

        if (countMap.size() == 2) {
            Integer[] freqs = countMap.keySet().toArray(new Integer[0]);
            int f1 = freqs[0];
            int c1 = countMap.get(f1);
            int f2 = freqs[1];
            int c2 = countMap.get(f2);

            if ((f1 == 1 && c1 == 1) || (f2 == 1 && c2 == 1)) {
                return true;
            }

            if ((f1 == f2 + 1 && c1 == 1) || (f2 == f1 + 1 && c2 == 1)) {
                return true;
            }
        }
        
        return false;
    }
}
```
### Algorithm
- Create a frequency array `freq` of size 26 to count character occurrences in `word`.
- Create a hash map `countMap` to store the frequency of frequencies (e.g., `countMap.get(k)` is the number of characters that appear `k` times).
- Populate `countMap` by iterating through the non-zero values in `freq`.
- If `countMap.size()` is 1:
    - Let the frequency be `f` and its count be `c`.
    - Return `true` if `f == 1` (e.g., "abcde") or `c == 1` (e.g., "aaaaa").
- If `countMap.size()` is 2:
    - Let the entries be `(f1, c1)` and `(f2, c2)`.
    - Return `true` if `(f1 == 1 && c1 == 1)` or `(f2 == 1 && c2 == 1)`. This covers removing a character that appears only once.
    - Return `true` if `(f1 == f2 + 1 && c1 == 1)` or `(f2 == f1 + 1 && c2 == 1)`. This covers reducing the frequency of a single character to match the others.
- In all other cases (e.g., `countMap.size() > 2`), return `false`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool equalFrequency(string word) {
    int cnt[26]{};
    for (char &c : word) {
      ++cnt[c - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      if (cnt[i]) {
        --cnt[i];
        int x = 0;
        bool ok = true;
        for (int v : cnt) {
          if (v == 0) {
            continue;
          }
          if (x && v != x) {
            ok = false;
            break;
          }
          x = v;
        }
        if (ok) {
          return true;
        }
        ++cnt[i];
      }
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def equalFrequency(self, word: str) -> bool: cnt = Counter(word) for c in cnt . keys(): cnt[c] -= 1 if len(set(v for v in cnt . values() if v)) == 1: return True cnt[c] += 1 return False

```