Minimum Deletion Cost to Make All Characters Equal solution and explanation
9 more videos on this problem
3784. Minimum Deletion Cost to Make All Characters Equal | Weekly Contest 481 | LeetcodeRapid Syntax · 8:59 · 261 views
Minimum Deletion Cost to Make All Characters Equal 🔥 LeetCode 3784 | Weekly Contest 481 | Greedy Study Placement · 6:13 · 213 views
Leetcode Weekly Contest 481 Q2. Minimum Deletion Cost to Make All Characters Equal #python #dsaADevOpsEngineer · 3:16 · 197 views
Leetcode 3784. Minimum Deletion Cost to Make All Characters Equal | Greedy | Map | O(N) | MediumLeet's Code · 22:05 · 98 views
Minimum Deletion Cost to Make All Characters Equal || Q2 || Weekly Contest 481ExpertFunda · 18:07 · 98 views
3784. Minimum Deletion Cost to Make All Characters Equal (Leetcode Medium)Programming Live with Larry · 5:46 · 61 views
LeetCode 3784 | Minimum Deletion Cost to Make All Characters Equal | JavaCode Kage · 4:45 · 58 views
LeetCode 3783 & 3784 | Weekly Contest 481 | Mirror Distance & Minimum Deletion CostProof2Code · 12:12 · 56 views
Weekly Contest 481 Minimum Deletion Cost to Make All Characters EqualR Sai Siddhu · 6:34 · 51 views
3784. Minimum Deletion Cost to Make All Characters Equal LeetCode 481 C++ Hashmap Easiest Hindi SolnBEASTCODES · 9:59 · 21 views
The problem
You are given a string s of length n and an integer array cost of the same length, where cost[i] is the cost to delete the ith character of s.
You may delete any number of characters from s (possibly none), such that the resulting string is non-empty and consists of equal characters.
Return an integer denoting the minimum total deletion cost required.
Example 1:
Input: s = "aabaac", cost = [1,2,3,4,1,10]
Output: 11
Explanation:
Deleting the characters at indices 0, 1, 2, 3, 4 results in the string "c", which consists of equal characters, and the total cost is cost[0] + cost[1] + cost[2] + cost[3] + cost[4] = 1 + 2 + 3 + 4 + 1 = 11.
Example 2:
Input: s = "abc", cost = [10,5,8]
Output: 13
Explanation:
Deleting the characters at indices 1 and 2 results in the string "a", which consists of equal characters, and the total cost is cost[1] + cost[2] = 5 + 8 = 13.
Example 3:
Input: s = "zzzzz", cost = [67,67,67,67,67]
Output: 0
Explanation:
All characters in s are equal, so the deletion cost is 0.
Constraints:
n == s.length == cost.length1 <= n <= 1051 <= cost[i] <= 109sconsists of lowercase English letters.
Approach overview
Problem Overview: You are given a string and a deletion cost for each character. Delete characters so that every remaining character in the string is the same. The goal is to minimize the total deletion cost.
Approach 1: Enumerate Target Character with Cost Grouping (O(n) time, O(k) space)
The key observation: the final string must contain only one distinct character. Instead of thinking about which characters to delete, think about which character you want to keep. For each character c, keep all occurrences of c and delete every other character. Use a hash map to accumulate the total cost associated with each character while iterating through the string.
Compute the total deletion cost of the entire string. Then track how much cost is associated with each character type. If you keep character c, you avoid deleting those positions, meaning the deletion cost becomes totalCost - costOf[c]. Iterate through all unique characters and choose the minimum possible deletion cost.
This works because keeping more occurrences of a character always reduces the deletion cost. The optimal strategy is simply to keep the character whose total cost contribution is the largest. A hash table makes grouping efficient, while iterating through the string once collects all required information.
Recommended for interviews: The grouping + enumeration approach is what interviewers expect. It demonstrates that you reframed the problem from “which characters to delete” into “which character to keep”. The implementation uses a simple array traversal and hash map aggregation, achieving linear time and minimal extra space.
Solution
We calculate the total deletion cost for each character in the string and store it in a hash table g, where the key is the character and the value is the corresponding total deletion cost. We also calculate the total cost tot of deleting all characters.
Next, we iterate through the hash table g. For each character c, we calculate the minimum deletion cost required to keep that character, which is tot - g[c]. The final answer is the minimum of all the minimum deletion costs corresponding to each character.
The time complexity is O(n) and the space complexity is O(|\Sigma|), where n is the length of the string s, and \Sigma is the set of distinct characters in the string.
class Solution:
def minCost(self, s: str, cost: List[int]) -> int:
tot = 0
g = defaultdict(int)
for c, v in zip(s, cost):
tot += v
g[c] += v
return min(tot - x for x in g.values())class Solution {
public long minCost(String s, int[] cost) {
long tot = 0;
Map<Character, Long> g = new HashMap<>(26);
for (int i = 0; i < cost.length; ++i) {
tot += cost[i];
g.merge(s.charAt(i), (long) cost[i], Long::sum);
}
long ans = tot;
for (long v : g.values()) {
ans = Math.min(ans, tot - v);
}
return ans;
}
}class Solution {
public:
long long minCost(string s, vector<int>& cost) {
long long tot = 0;
unordered_map<char, long long> g;
for (int i = 0; i < cost.size(); ++i) {
tot += cost[i];
g[s[i]] += cost[i];
}
long long ans = tot;
for (auto [_, v] : g) {
ans = min(ans, tot - v);
}
return ans;
}
};function minCost(s: string, cost: number[]): number {
let tot = 0;
const g: Map<string, number> = new Map();
for (let i = 0; i < s.length; i++) {
const c = s[i];
const v = cost[i];
tot += v;
g.set(c, (g.get(c) ?? 0) + v);
}
let ans = tot;
for (const x of g.values()) {
ans = Math.min(ans, tot - x);
}
return ans;
}func minCost(s string, cost []int) int64 {
tot := int64(0)
g := map[byte]int64{}
for i, v := range cost {
tot += int64(v)
g[s[i]] += int64(v)
}
ans := tot
for _, x := range g {
ans = min(ans, tot-x)
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Character Enumeration | O(n * k) | O(1) | When alphabet size is extremely small and clarity matters more than efficiency |
| Grouping + Enumeration with Hash Map | O(n) | O(k) | General case. Efficient for large strings and multiple character types |
Frequently asked questions
Is Minimum Deletion Cost to Make All Characters Equal easy or hard?
The problem is typically classified as Medium. The implementation is straightforward once you recognize that the optimal strategy is to keep one character type and delete the rest. The challenge lies in identifying the cost-aggregation trick that reduces the problem to a single pass.
Minimum Deletion Cost to Make All Characters Equal Python/Java solution
The solution iterates through the string and stores the total deletion cost per character in a dictionary (Python) or HashMap (Java). After computing the total cost of all characters, subtract the maximum stored value from the total. This produces the minimum cost needed to delete the remaining characters.
How to solve Minimum Deletion Cost to Make All Characters Equal in O(n)?
Traverse the string once and use a hash map to sum the deletion cost for each character. Also compute the total cost of all characters. The minimum deletion cost equals totalCost minus the maximum accumulated cost of any single character. This keeps the most valuable character group and deletes the rest.
What is the best approach for Minimum Deletion Cost to Make All Characters Equal?
The optimal approach is grouping characters using a hash map and enumerating which character to keep. First compute the total deletion cost of the string, then track the total cost associated with each character. Keeping the character with the maximum accumulated cost minimizes deletions. This runs in O(n) time with O(k) extra space, where k is the number of distinct characters.
Is Minimum Deletion Cost to Make All Characters Equal asked at Google/Amazon/Meta?
Problems based on cost minimization, string grouping, and hash map aggregation frequently appear in interviews at companies like Amazon, Google, and Meta. Variants often involve choosing a target value and minimizing operations or costs across the rest of the array or string.
What data structure is used in Minimum Deletion Cost to Make All Characters Equal?
The core data structure is a hash table (hash map) that groups characters and accumulates their total deletion costs. This allows constant-time updates while iterating through the string and makes it easy to evaluate which character should be kept.
What is the time complexity of Minimum Deletion Cost to Make All Characters Equal?
The optimal solution runs in O(n) time because the string is scanned once to accumulate costs per character. A second pass over the distinct characters determines the minimum deletion cost. Space complexity is O(k) for storing cost totals of each unique character.