Minimum Operations to Make Character Frequencies Equal - Video Solutions
3389. Minimum Operations to Make Character Frequencies Equal (Leetcode Hard)
Minimum Operations to Make Character Frequencies Equal - Video Solution
Watch 5 video solutions for Minimum Operations to Make Character Frequencies Equal, a hard level problem involving Hash Table, String, Dynamic Programming. This walkthrough by Programming Live with Larry has 750 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a string s.
A string t is called good if all characters of t occur the same number of times.
You can perform the following operations any number of times:
- Delete a character from
s. - Insert a character in
s. - Change a character in
sto its next letter in the alphabet.
Note that you cannot change 'z' to 'a' using the third operation.
Return the minimum number of operations required to make s good.
Example 1:
Input: s = "acab"
Output: 1
Explanation:
We can make s good by deleting one occurrence of character 'a'.
Example 2:
Input: s = "wddw"
Output: 0
Explanation:
We do not need to perform any operations since s is initially good.
Example 3:
Input: s = "aaabc"
Output: 2
Explanation:
We can make s good by applying these operations:
- Change one occurrence of
'a'to'b' - Insert one occurrence of
'c'intos
Constraints:
3 <= s.length <= 2 * 104scontains only lowercase English letters.
Approach Overview
Problem Overview: You are given a string and can perform operations that insert, delete, or convert characters. The goal is to make every character that appears in the string have the same frequency with the minimum number of operations.
Approach 1: Frequency Enumeration with Greedy Balancing (O(26 * maxFreq) time, O(1) space)
Start with a counting pass to compute the frequency of each character (26 lowercase letters). The key observation: in the final string, every used character must appear exactly k times. Enumerate all possible target frequencies k from 1 to the maximum existing frequency. For each character count c, compute the cheapest way to reach k: delete extra characters if c > k, insert missing characters if c < k, or convert surplus characters from one letter into deficits of another. Greedily match surplus counts with deficits to minimize operations. The minimal cost across all k values is the answer.
Approach 2: Dynamic Programming on Alphabet Frequencies (O(26 * maxFreq) time, O(26) space)
After computing character counts using a hash table or fixed array, iterate over possible target frequencies k. For each letter, decide whether to delete all occurrences, keep exactly k, or convert extra characters to help satisfy deficits in other letters. A small dynamic programming state tracks the minimum cost while processing the alphabet left to right, carrying over surplus characters that can be converted later. This avoids double‑counting conversions and guarantees the minimum operations for each target frequency.
Approach 3: Brute Force Enumeration of Target Sets (O(2^26) theoretical, impractical)
A naive formulation tries every subset of characters that will remain in the final string and forces each chosen character to have the same frequency. For each subset, compute the cost to insert, delete, or convert characters accordingly. While this clarifies the structure of the problem, the search space is exponential and not feasible in practice.
Recommended for interviews: Enumerating the target frequency combined with counting and greedy balancing is the expected solution. It shows you recognize that the final state must use a single frequency k and reduces the problem to evaluating costs for each candidate. The dynamic programming variant demonstrates deeper control over conversions between characters, which interviewers often appreciate for hard string optimization problems.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Enumeration + Greedy | O(26 * maxFreq) | O(1) | Best general solution for lowercase strings; simple and efficient |
| Dynamic Programming on Frequencies | O(26 * maxFreq) | O(26) | When carefully tracking conversions between surplus and deficit characters |
| Subset Brute Force | O(2^26) | O(1) | Conceptual baseline; not practical for real inputs |