Skip to content

3784. Minimum Deletion Cost to Make All Characters Equal

Description

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.

Solutions

Solution 1: Grouping + Enumeration

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 \(\textit{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 \(\textit{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.

1
2
3
4
5
6
7
8
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())

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
}

Comments