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

Thinking

The leftover string must be nonempty and monochromatic, i.e. we delete every other character. The cost of keeping letter \(c\) is the total cost minus the cost of all \(c\)s; we take the minimum over \(c\).

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