Minimum Deletion Cost to Make All Characters Equal - Video Solutions

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.