2423. Remove Letter To Equalize Frequency
Problem Description
In this problem, we are dealing with a string word
that is made up of lowercase English letters. The objective is to find if it's possible to remove one letter from this string such that the remaining letters all have the same frequency. In other words, after removing one letter, each of the remaining letters should appear the same number of times in the adjusted string.
For example, consider the string "aabbcc". If we remove one 'c', we will have "aabb" left, where 'a' and 'b' each appear twice, meeting the condition for equal frequency.
Important points to note from the problem:
- The given string uses a 0-based index, meaning the first character has an index of 0.
- We are required to remove exactly one letter, and doing nothing is not an option.
- We need to check the frequencies of the letters present after the removal and are only concerned with those letters that would still exist in the string.
Intuition
To solve this problem, the intuition is to iterate through each letter in the word, simulate the removal of that letter, and check the frequencies of the remaining letters to see if they all match. The solution is implemented as follows:
-
Use a counter to track the frequency of each letter in the original word.
-
Iterate through each letter, decrement its count in the counter (simulating its removal), and check if all the other counts are the same.
-
If after removing a letter, all other letters have the same count, it means it is possible to have equal frequency by removing one letter, so return
True
. -
If the condition is not met, restore the count of the removed letter back before moving onto the next letter.
-
If no removal results in equal frequencies, return
False
.
This approach works because by decrementing the count of each letter one at a time, we check every possible scenario of the word with one less letter. As soon as we find one situation where all other letter counts match, we have our solution. If no such case exists, the requirement cannot be met.
Solution Approach
The implementation of the solution is straightforward, leveraging Python's Counter
from the collections module, which is essentially a specialized dictionary used to count hashable objects.
Here's a step-by-step walk-through of the algorithm:
-
We initialize a
Counter
object with theword
as an argument to count the frequency of each letter present in theword
. -
The function then enters a loop, iterating through the keys in the counter (which represent unique letters in the word), and for each iteration:
-
The frequency of the current letter is decreased by one, simulating its removal. This is done using
cnt[c] -= 1
. -
We then check if the frequencies match for all the remaining letters. To do this concisely, we:
- Construct a set comprehension
set(v for v in cnt.values() if v)
which:- Loops through all frequency values in the counter.
- Includes a value in the set if it is non-zero (since a frequency dropping to zero implies the letter is effectively removed from the word).
- Creates a set so that any duplicates are removed and only unique frequency values remain.
- If the resulting set has only one element, it means all remaining letters have the same frequency.
- Construct a set comprehension
-
If this condition is met, we return
True
immediately, indicating success. -
If the condition is not met, we restore the frequency of the current letter before moving on to the next one with
cnt[c] += 1
. This step is crucial to ensure that the next iteration starts with the original frequencies, minus the next letter to simulate its removal.
-
-
If the loop completes and no return statement has been executed, this implies no single removal could achieve the desired equal frequency of letters. In this case, the function returns
False
.
This solution approach effectively employs the counter to test each possible single-letter removal and leverages Python's set to efficiently check for equal frequencies after each removal.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider the string word = "aabbccd"
. We want to determine if it's possible to remove one letter from this string so that the remaining letters all have the same frequency.
-
First, we initialize a
Counter
object with the string. Forword = "aabbccd"
, the counter would look like this:Counter({'a': 2, 'b': 2, 'c': 2, 'd': 1})
. This means 'a' appears twice, 'b' appears twice, 'c' appears twice, and 'd' appears once. -
We then enter a loop to iterate through the keys in the counter.
-
For the first iteration, we begin with the letter 'a', decreasing its count by one, resulting in
Counter({'a': 1, 'b': 2, 'c': 2, 'd': 1})
. -
We construct a set from the values of the counter, excluding any zeros:
{1, 2}
. Since the set has more than one unique value, the condition for all letters to have the same frequency isn't met with the removal of 'a'. -
We restore the count of 'a' back to its original value and move on to the next letter:
Counter({'a': 2, 'b': 2, 'c': 2, 'd': 1})
. -
Next, we simulate removing one 'b', we get
Counter({'a': 2, 'b': 1, 'c': 2, 'd': 1})
. The set of frequencies would again be{1, 2}
, so the condition is not met and we restore 'b'. -
We proceed through the letters. When we decrement 'c', we get
Counter({'a': 2, 'b': 2, 'c': 1, 'd': 1})
and a set of frequencies{1, 2}
. We restore 'c' and continue. -
Finally, we simulate removing 'd'. This results in
Counter({'a': 2, 'b': 2, 'c': 2, 'd': 0})
. The frequency set would be{2}
, since we exclude the zero frequency of 'd' (it is as if 'd' has been removed from the word). This set contains one unique value, implying all remaining letters have the same frequency. -
Since we've found a case where removing one letter results in equal frequencies for the remaining letters, we return
True
. It is indeed possible to remove one letter from "aabbccd" to make all remaining letters have the same frequency.
This walkthrough illustrates how the solution approach tests different scenarios by removing each letter one by one and checking if the frequencies of the remaining letters match.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def equalFrequency(self, word: str) -> bool:
5 # Create a counter for all characters in the word
6 char_count = Counter(word)
7
8 # Iterate through each character in the counter
9 for char in char_count.keys():
10 # Decrement the character's count by 1
11 char_count[char] -= 1
12
13 # Generate a set of all non-zero counts in the counter
14 unique_counts = set(count for count in char_count.values() if count)
15
16 # Check if all remaining character counts are the same
17 if len(unique_counts) == 1:
18 return True
19
20 # Restore the original count for the character
21 char_count[char] += 1
22
23 # Return False if no condition satisfies the equal frequency requirement
24 return False
25
1class Solution {
2 public boolean equalFrequency(String word) {
3 // Frequency array to hold the count of each character in the word
4 int[] freq = new int[26];
5
6 // Count the frequency of each character in the word
7 for (int i = 0; i < word.length(); ++i) {
8 freq[word.charAt(i) - 'a']++;
9 }
10
11 // Iterate through each character in the alphabet
12 for (int i = 0; i < 26; ++i) {
13 // If the current character is present in the word
14 if (freq[i] > 0) {
15 // Decrease the frequency of the character by 1
16 freq[i]--;
17
18 int targetFreq = 0; // The target frequency all characters should have
19 boolean isValid = true; // Flag to check if the current modification leads to equal frequencies
20
21 // Check if after removing one character, the rest have the same frequency
22 for (int v : freq) {
23 if (v == 0) {
24 continue; // Skip if the character is not in the word
25 }
26 if (targetFreq > 0 && v != targetFreq) {
27 isValid = false; // Frequencies differ, set flag to false
28 break;
29 }
30 targetFreq = v; // Set the current frequency as the target for others to match
31 }
32
33 // If removing one occurrence of this character results in all other characters having the same frequency
34 if (isValid) {
35 return true;
36 }
37
38 // Undo the frequency change as we move on to the next character
39 freq[i]++;
40 }
41 }
42
43 // If no single removal leads to equal frequencies, return false
44 return false;
45 }
46}
47
1class Solution {
2public:
3 bool equalFrequency(string word) {
4 int counts[26] = {0}; // Initialize an array to store the frequency of each letter
5
6 // Populate the frequency array with counts of each character in the word
7 for (char& c : word) {
8 ++counts[c - 'a'];
9 }
10
11 // Iterate through the alphabet
12 for (int i = 0; i < 26; ++i) {
13 if (counts[i]) { // Check if the current letter has a non-zero frequency
14 --counts[i]; // Decrementing the count to check if we can equalize frequency by removing one
15
16 // Initialize a variable to store the frequency to compare against
17 int target_frequency = 0;
18 bool can_equalize = true; // Flag to check if equal frequency can be achieved
19
20 // Iterate through the counts array to check the frequencies
21 for (int count : counts) {
22 if (count == 0) {
23 continue; // Skip if the count is zero
24 }
25
26 // If we have already set the frequency to compare and current one doesn't match
27 if (target_frequency && count != target_frequency) {
28 can_equalize = false; // We cannot equalize the frequencies
29 break;
30 }
31
32 // If this is the first non-zero frequency we see, we set it as the target frequency
33 target_frequency = count;
34 }
35
36 // Checking if we can equalize the frequency by the removal of one character
37 if (can_equalize) {
38 return true;
39 }
40
41 // Restore the count after checking
42 ++counts[i];
43 }
44 }
45
46 // If no equal frequency is possible by the removal of one character
47 return false;
48 }
49};
50
1function equalFrequency(word: string): boolean {
2 // Initialize a count array of length 26 to store the frequency of each letter,
3 // assuming 'a' maps to index 0 and 'z' maps to index 25.
4 const charFrequency: number[] = new Array(26).fill(0);
5
6 // Populate the charFrequency array with the count of each character in the word.
7 for (const char of word) {
8 charFrequency[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
9 }
10
11 // Iterate through each character's frequency.
12 for (let i = 0; i < 26; ++i) {
13 if (charFrequency[i]) {
14 // Decrement the frequency of the current character to check if
15 // we can achieve equal frequency by removing one char occurrence.
16 charFrequency[i]--;
17
18 // Initialize a variable to store the frequency of the first non-zero character we encounter.
19 let commonFrequency = 0;
20 let allFrequenciesEqual = true;
21
22 // Iterate through the frequencies to check if they are all the same.
23 for (const frequency of charFrequency) {
24 if (frequency === 0) {
25 continue; // Skip if frequency is 0 as we are looking for non-zero frequencies.
26 }
27 // If commonFrequency is set and current frequency is different, set the equal flag to false.
28 if (commonFrequency && frequency !== commonFrequency) {
29 allFrequenciesEqual = false;
30 break;
31 }
32 // Update commonFrequency with the current non-zero frequency.
33 commonFrequency = frequency;
34 }
35
36 // If all non-zero frequencies are equal, return true.
37 if (allFrequenciesEqual) {
38 return true;
39 }
40 // Since we modified the original frequency, restore it back.
41 charFrequency[i]++;
42 }
43 }
44
45 // If we did not find any instance where all non-zero frequencies
46 // were equal after removing one char occurrence, return false.
47 return false;
48}
49
Time and Space Complexity
Time Complexity
The time complexity of the provided code is determined by several factors:
-
Building the
cnt
dictionary based on theCounter
class, which requires iterating over every character in the word, results in aO(n)
operation wheren
is the length of the word. -
The
for
loop in the code iterates over each character in the unique set of characters of theword
. Ifk
is the number of unique characters, this results in up toO(k)
iterations. -
Inside the loop, updating a count in the dictionary is an
O(1)
operation. -
The
set
andlist
comprehension iterates over the values ofcnt
, which is alsoO(k)
, as it is done for each character in unique set. -
The condition
len(set(v for v in cnt.values() if v)) == 1
is essentially checking if all non-zero values in the cnt dictionary are equal, which takes up toO(k)
time to compute since it involves iteration over all values to form a set and then checking its length.
Combining these factors, the overall time complexity is O(n + k^2)
. In the worst case, if all characters are unique, k
is equal to n
, this simplifies to O(n^2)
.
Space Complexity
For space complexity:
-
The
cnt
dictionary stores counts of unique characters, so it takes upO(k)
space wherek
is the number of unique characters. -
The set and list comprehensions create temporary sets and lists that can contain up to
k
elements. However, these are temporary and not stored, so they don't add to the space complexity asymptotically.
Summarizing, the overall space complexity is O(k)
. In the worst case scenario, k = n
, which yields O(n)
for the space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!