Skip to main content
Talentd

Minimum Deletion Cost to Make All Characters Equal - Solution & Explanation

MediumArrayHash TableStringEnumeration7 min read
Practice this problem

Problem Statement

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.length
  • 1 <= n <= 105
  • 1 <= cost[i] <= 109
  • s consists 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Character EnumerationO(n * k)O(1)When alphabet size is extremely small and clarity matters more than efficiency
Grouping + Enumeration with Hash MapO(n)O(k)General case. Efficient for large strings and multiple character types

Video Solution

3784. Minimum Deletion Cost to Make All Characters Equal | Weekly Contest 481 | Leetcode • Rapid Syntax • 261 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Deletion Cost to Make All Characters Equal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays