3784. Minimum Deletion Cost to Make All Characters Equal

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 i^th 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.

Key Insight

The solution requires understanding these crucial observations:

1. The resulting string must consist of only one character type (all 'a's, all 'b's, etc.)
2. We can delete any characters, but must keep at least one character (non-empty result)
3. To minimize deletion cost, we should keep the character with the highest total deletion cost
4. If we choose character ch to keep, we must delete all characters that are not ch
5. Equivalently, we can think: minimum deletion cost = total cost - max(cost_sum for each character)

Alternative approach: For each group of consecutive identical characters, keep only the most expensive one in that group and delete the rest.

Approach 1: Frequency Array (Your Approach - Optimal)

Calculate the total cost of deleting all characters, then for each character (a-z), calculate the total cost of keeping that character. The minimum deletion cost is total cost minus the maximum keep cost.

Algorithm Steps

1. Initialize total = 0 and freq[26] = {0}
2. For each character in s:
   • Add cost[i] to total
   • Add cost[i] to freq[s[i] - 'a']
3. Find max_freq = max(freq[0..25])
4. Return total - max_freq

How It Works

For each character from 'a' to 'z', freq[ch] represents the cost of keeping all occurrences of that character. If we choose to keep character ch, we must delete all other characters at cost total - freq[ch]. We want to minimize this, which means maximizing freq[ch].

Complexity Analysis

Where n is the length of the string. Single pass through the string with constant extra space for the frequency array.

class Solution {
public:
    long long minCost(string s, vector<int>& cost) {
        long long total = 0;
        vector<long long> freq(26, 0);
        
        for (int i = 0; i < s.length(); i++) {
            total += cost[i];
            freq[s[i] - 'a'] += cost[i];
        }
        
        long long max_freq = 0;
        for (int i = 0; i < 26; i++) {
            if (freq[i] > max_freq) {
                max_freq = freq[i];
            }
        }
        
        return total - max_freq;
    }
};

class Solution {
    public long minCost(String s, int[] cost) {
        long total = 0;
        long[] freq = new long[26];
        
        for (int i = 0; i < s.length(); i++) {
            total += cost[i];
            freq[s.charAt(i) - 'a'] += cost[i];
        }
        
        long maxFreq = 0;
        for (int i = 0; i < 26; i++) {
            if (freq[i] > maxFreq) {
                maxFreq = freq[i];
            }
        }
        
        return total - maxFreq;
    }
}

class Solution:
    def minCost(self, s: str, cost: list[int]) -> int:
        total = 0
        freq = [0] * 26
        
        for i in range(len(s)):
            total += cost[i]
            freq[ord(s[i]) - ord('a')] += cost[i]
        
        max_freq = max(freq)
        return total - max_freq

Approach 2: Greedy by Character Groups

Process the string in groups of consecutive identical characters. For each group, keep only the character with the maximum cost and delete the rest.

Algorithm Steps

1. Initialize total_cost = 0 and i = 0
2. While i < n:
   • Start new group with character s[i]
   • Track group_max = cost[i] and group_sum = cost[i]
   • Move i to next character while same character
   • For each same character, update group_max and group_sum
   • Add group_sum - group_max to total_cost (delete all but max)
3. Return total_cost

How It Works

This approach works because in the final string, all characters must be equal. If we have consecutive identical characters, we need to keep only one of them (the most expensive) to minimize cost. For different characters in different groups, we'll eventually need to delete entire groups except for one character type.

Complexity Analysis

Single pass through the string with constant extra variables.

class Solution {
public:
    long long minCost(string s, vector<int>& cost) {
        long long total = 0;
        int n = s.length();
        int i = 0;
        
        while (i < n) {
            char current_char = s[i];
            long long group_sum = 0;
            long long group_max = 0;
            
            // Process all consecutive same characters
            while (i < n && s[i] == current_char) {
                group_sum += cost[i];
                if (cost[i] > group_max) {
                    group_max = cost[i];
                }
                i++;
            }
            
            // Add cost of deleting all but the most expensive in this group
            total += (group_sum - group_max);
        }
        
        return total;
    }
};

class Solution {
    public long minCost(String s, int[] cost) {
        long total = 0;
        int n = s.length();
        int i = 0;
        
        while (i < n) {
            char currentChar = s.charAt(i);
            long groupSum = 0;
            long groupMax = 0;
            
            // Process all consecutive same characters
            while (i < n && s.charAt(i) == currentChar) {
                groupSum += cost[i];
                if (cost[i] > groupMax) {
                    groupMax = cost[i];
                }
                i++;
            }
            
            // Add cost of deleting all but the most expensive in this group
            total += (groupSum - groupMax);
        }
        
        return total;
    }
}

class Solution:
    def minCost(self, s: str, cost: list[int]) -> int:
        total = 0
        n = len(s)
        i = 0
        
        while i < n:
            current_char = s[i]
            group_sum = 0
            group_max = 0
            
            # Process all consecutive same characters
            while i < n and s[i] == current_char:
                group_sum += cost[i]
                group_max = max(group_max, cost[i])
                i += 1
            
            # Add cost of deleting all but the most expensive in this group
            total += (group_sum - group_max)
        
        return total

Approach 3: Dynamic Programming (Alternative)

Use dynamic programming to track the minimum cost to make all characters equal up to position i, considering which character we keep.

Algorithm Steps

1. Initialize dp[26] where dp[ch] = minimum cost to make all characters equal to character ch
2. For each character s[i] with cost cost[i]:
   • If we keep character s[i], we don't delete it (cost 0 for this character if it matches target)
   • If we change to different character, we must delete s[i] (add cost[i])
3. Update DP table accordingly
4. Return minimum from dp[0..25]

How It Works

For each character position, we consider keeping each possible character (a-z). If the current character matches our target, we don't pay deletion cost. Otherwise, we add the deletion cost.

Complexity Analysis

Where n is the length of string. This is less efficient than Approach 1 but demonstrates the DP pattern.

class Solution {
public:
    long long minCost(string s, vector<int>& cost) {
        int n = s.length();
        
        // dp[ch] = minimum cost to make all characters equal to character 'a' + ch
        vector<long long> dp(26, 0);
        
        for (int i = 0; i < n; i++) {
            int current_char = s[i] - 'a';
            
            // Temporary array for new DP values
            vector<long long> new_dp(26, LLONG_MAX);
            
            for (int ch = 0; ch < 26; ch++) {
                if (dp[ch] == LLONG_MAX) continue;
                
                if (ch == current_char) {
                    // Current character matches target, keep it (no cost)
                    new_dp[ch] = min(new_dp[ch], dp[ch]);
                } else {
                    // Current character doesn't match, delete it
                    new_dp[ch] = min(new_dp[ch], dp[ch] + cost[i]);
                }
            }
            
            dp = new_dp;
        }
        
        // Find minimum cost among all possible target characters
        long long min_cost = LLONG_MAX;
        for (int ch = 0; ch < 26; ch++) {
            min_cost = min(min_cost, dp[ch]);
        }
        
        return min_cost;
    }
};

class Solution {
    public long minCost(String s, int[] cost) {
        int n = s.length();
        
        // dp[ch] = minimum cost to make all characters equal to character 'a' + ch
        long[] dp = new long[26];
        Arrays.fill(dp, Long.MAX_VALUE);
        
        for (int i = 0; i < n; i++) {
            int currentChar = s.charAt(i) - 'a';
            long[] newDp = new long[26];
            Arrays.fill(newDp, Long.MAX_VALUE);
            
            for (int ch = 0; ch < 26; ch++) {
                if (dp[ch] == Long.MAX_VALUE) continue;
                
                if (ch == currentChar) {
                    // Current character matches target, keep it (no cost)
                    newDp[ch] = Math.min(newDp[ch], dp[ch]);
                } else {
                    // Current character doesn't match, delete it
                    newDp[ch] = Math.min(newDp[ch], dp[ch] + cost[i]);
                }
            }
            
            dp = newDp;
        }
        
        // Find minimum cost among all possible target characters
        long minCost = Long.MAX_VALUE;
        for (int ch = 0; ch < 26; ch++) {
            minCost = Math.min(minCost, dp[ch]);
        }
        
        return minCost;
    }
}

class Solution:
    def minCost(self, s: str, cost: list[int]) -> int:
        n = len(s)
        
        # dp[ch] = minimum cost to make all characters equal to character ch
        dp = [float('inf')] * 26
        
        for i in range(n):
            current_char = ord(s[i]) - ord('a')
            new_dp = [float('inf')] * 26
            
            for ch in range(26):
                if dp[ch] == float('inf'):
                    continue
                
                if ch == current_char:
                    # Current character matches target, keep it (no cost)
                    new_dp[ch] = min(new_dp[ch], dp[ch])
                else:
                    # Current character doesn't match, delete it
                    new_dp[ch] = min(new_dp[ch], dp[ch] + cost[i])
            
            dp = new_dp
        
        # Find minimum cost among all possible target characters
        min_cost = min(dp)
        return min_cost

Visual Example Walkthrough

Let's trace through Approach 1 with s = "aabaac", cost = [1,2,3,4,1,10]:

Comparison of Approaches

Edge Cases and Testing

1. All Characters Same

Input: s = "aaaaa", cost = [1,2,3,4,5] → Output: 0
All characters are already equal, no deletion needed
Frequency array: 'a' = 15, total = 15, result = 15 - 15 = 0

2. Single Character

Input: s = "a", cost = [100] → Output: 0
Only one character, must keep it (non-empty result)
Frequency array: 'a' = 100, total = 100, result = 100 - 100 = 0

3. All Different Characters

Input: s = "abcde", cost = [10,20,30,40,50] → Output: 100
Total = 10+20+30+40+50 = 150
Max frequency: max(10,20,30,40,50) = 50 (for 'e')
Result = 150 - 50 = 100
Keep 'e', delete others

4. Two Characters with Equal Total Cost

Input: s = "abab", cost = [5,5,5,5] → Output: 10
Total = 20
'a' total = 5+5 = 10
'b' total = 5+5 = 10
Result = 20 - 10 = 10 (can keep either 'a' or 'b')

5. Very Large Costs

Input: s = "ab", cost = [10^9, 10^9] → Output: 10^9
Total = 2×10^9
'a' = 10^9, 'b' = 10^9
Result = 2×10^9 - 10^9 = 10^9
Must use 64-bit integers to avoid overflow

6. Consecutive Identical Characters

Input: s = "aaabbb", cost = [1,2,3,4,5,6] → Output: 10
Greedy approach: 
  Group 'aaa': keep max=3, delete 1+2 = 3
  Group 'bbb': keep max=6, delete 4+5 = 9
  Total = 3 + 9 = 12? Wait, this is wrong
  
Frequency approach:
  Total = 1+2+3+4+5+6 = 21
  'a' = 1+2+3 = 6
  'b' = 4+5+6 = 15
  Result = 21 - 15 = 6 (keep 'b', delete all 'a's)

FAQs