跳转至

1647. 字符频次唯一的最小删除次数

来源第 214 场周赛 Q2难度中等分数1509

题目描述

如果字符串 s 中 不存在 两个不同字符 频次 相同的情况，就称 s 是 优质字符串 。

给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的 最小 字符数。

字符串中字符的 频次 是该字符在字符串中的出现次数。例如，在字符串 "aab" 中，'a' 的频次是 2，而 'b' 的频次是 1 。

 

示例 1：

输入：s = "aab"
输出：0
解释：s 已经是优质字符串。

示例 2：

输入：s = "aaabbbcc"
输出：2
解释：可以删除两个 'b' , 得到优质字符串 "aaabcc" 。
另一种方式是删除一个 'b' 和一个 'c' ，得到优质字符串 "aaabbc" 。

示例 3：

输入：s = "ceabaacb"
输出：2
解释：可以删除两个 'c' 得到优质字符串 "eabaab" 。
注意，只需要关注结果字符串中仍然存在的字符。（即，频次为 0 的字符会忽略不计。）

 

提示：

  • 1 <= s.length <= 105
  • s 仅含小写英文字母

解法

方法一：数组 + 排序

思考

要使各字母频次互异，只能删字符从而降低频次。字母种类只有 \(26\)，把频次从大到小排列后，每个值至多占用一个整数槽。

维护下一个仍可用的上限 \(\textit{pre}\)：若当前频次 \(v \ge \textit{pre}\)，必须删到 \(\textit{pre}-1\)（若 \(\textit{pre}\) 已到 \(0\) 则全部删掉）。

否则该频次可原样保留，并把 \(\textit{pre}\) 改成 \(v\)。

我们先用一个长度为 \(26\) 的数组 \(\textit{cnt}\) 统计字符串 \(s\) 中每个字母出现的次数。

然后我们对数组 \(\textit{cnt}\) 进行倒序排序。定义一个变量 \(\textit{pre}\) 记录当前字母的出现次数。

接下来，遍历数组 \(\textit{cnt}\) 每个元素 \(v\)，如果当前 \(\textit{pre}\) 等于 \(0\)，我们直接将答案加上 \(v\)；否则，如果 \(v \geq \textit{pre}\)，我们将答案加上 \(v-\textit{pre}+1\)，并且将 \(\textit{pre}\) 减去 \(1\)，否则，我们直接将 \(\textit{pre}\) 更新为 \(v\)。然后继续遍历下个元素。

遍历结束，返回答案即可。

时间复杂度 \(O(n + |\Sigma| \times \log |\Sigma|)\)，空间复杂度 \(O(|\Sigma|)\)。其中 \(n\) 是字符串 \(s\) 的长度，而 \(|\Sigma|\) 为字母集的大小。本题中 \(|\Sigma|=26\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def minDeletions(self, s: str) -> int:
        cnt = Counter(s)
        ans, pre = 0, inf
        for v in sorted(cnt.values(), reverse=True):
            if pre == 0:
                ans += v
            elif v >= pre:
                ans += v - pre + 1
                pre -= 1
            else:
                pre = v
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minDeletions(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        Arrays.sort(cnt);
        int ans = 0, pre = 1 << 30;
        for (int i = 25; i >= 0; --i) {
            int v = cnt[i];
            if (pre == 0) {
                ans += v;
            } else if (v >= pre) {
                ans += v - pre + 1;
                --pre;
            } else {
                pre = v;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minDeletions(string s) {
        vector<int> cnt(26);
        for (char& c : s) ++cnt[c - 'a'];
        sort(cnt.rbegin(), cnt.rend());
        int ans = 0, pre = 1 << 30;
        for (int& v : cnt) {
            if (pre == 0) {
                ans += v;
            } else if (v >= pre) {
                ans += v - pre + 1;
                --pre;
            } else {
                pre = v;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func minDeletions(s string) (ans int) {
    cnt := make([]int, 26)
    for _, c := range s {
        cnt[c-'a']++
    }
    sort.Sort(sort.Reverse(sort.IntSlice(cnt)))
    pre := 1 << 30
    for _, v := range cnt {
        if pre == 0 {
            ans += v
        } else if v >= pre {
            ans += v - pre + 1
            pre--
        } else {
            pre = v
        }
    }
    return
}

方法二：贪心（相邻递减）

思考

方法一用全局上限约束。等价地，排序后保证相邻频次严格递减：后者若不低于前者就一直减一，累计减少量即删除数。

实现更贴近「相邻互异」，复杂度同阶。

同样先统计并倒序排序出现次数。从前往后看相邻频次，若当前频次不小于前一个，就逐次减 \(1\)，直到严格更小。

时间复杂度 \(O(n + |\Sigma| \times \log |\Sigma| + n)\)，空间复杂度 \(O(|\Sigma|)\)。其中 \(n\) 是字符串 \(s\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def minDeletions(self, s: str) -> int:
        cnt = Counter(s)
        vals = sorted(cnt.values(), reverse=True)
        ans = 0
        for i in range(1, len(vals)):
            while vals[i] >= vals[i - 1] and vals[i] > 0:
                vals[i] -= 1
                ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int minDeletions(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        Arrays.sort(cnt);
        int ans = 0;
        for (int i = 24; i >= 0; --i) {
            while (cnt[i] >= cnt[i + 1] && cnt[i] > 0) {
                --cnt[i];
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int minDeletions(string s) {
        vector<int> cnt(26);
        for (char& c : s) ++cnt[c - 'a'];
        sort(cnt.rbegin(), cnt.rend());
        int ans = 0;
        for (int i = 1; i < 26; ++i) {
            while (cnt[i] >= cnt[i - 1] && cnt[i] > 0) {
                --cnt[i];
                ++ans;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func minDeletions(s string) (ans int) {
    cnt := make([]int, 26)
    for _, c := range s {
        cnt[c-'a']++
    }
    sort.Sort(sort.Reverse(sort.IntSlice(cnt)))
    for i := 1; i < 26; i++ {
        for cnt[i] >= cnt[i-1] && cnt[i] > 0 {
            cnt[i]--
            ans++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function minDeletions(s: string): number {
    let map = {};
    for (let c of s) {
        map[c] = (map[c] || 0) + 1;
    }
    let ans = 0;
    let vals: number[] = Object.values(map);
    vals.sort((a, b) => a - b);
    for (let i = 1; i < vals.length; ++i) {
        while (vals[i] > 0 && i != vals.indexOf(vals[i])) {
            --vals[i];
            ++ans;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
impl Solution {
    #[allow(dead_code)]
    pub fn min_deletions(s: String) -> i32 {
        let mut cnt = vec![0; 26];
        let mut ans = 0;

        for c in s.chars() {
            cnt[((c as u8) - ('a' as u8)) as usize] += 1;
        }

        cnt.sort_by(|&lhs, &rhs| rhs.cmp(&lhs));

        for i in 1..26 {
            while cnt[i] >= cnt[i - 1] && cnt[i] > 0 {
                cnt[i] -= 1;
                ans += 1;
            }
        }

        ans
    }
}

评论