题目描述与示例

题目

删除字符串s中出现次数最少的字符，如果多个字符出现次数一样则都删除。

输入

输入只包含小写字母

输出描述

输出删除后剩余的字符串；若删除后字符串长度为0，则输出字符串"empty"

示例一

输入

abcdd

输出

dd

示例二

输入

aabbccdd

输出

empty

解题思路

为了删除掉字符串s中出现次数最少的字符，我们必须先统计s中的所有字母的出现个数，很容易想到使用哈希表的Counter()来完成这个功能。然后我们再统计哪些字母出现的次数为最小出现次数，用一个哈希集合记录这些需要删除的字母，再使用字符串的replace()方法或者join()方法即可完成删除。

本题显然也是哈希表在统计元素频率类型的题目中的典型应用。

代码

Python

# 题目：2023Q1A-删除最少字符
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：哈希表
# 代码看不懂的地方，请直接在群上提问

# 导入collections中的Counter计数器类，使用dict()也可以，但是代码就要多一些判断
from collections import Counter

# 输入原始字符串s
s = input()

# 直接调用Counter()计数器类，获得所有字符的频率
cnt = Counter(s)

# 获得所有频率中的最小值，即最小频率min_cnt
min_cnt = min(cnt.values())

# 如果某个字符ch的频率等于最小频率，则记录在哈希集合min_cnt_set中
min_cnt_set = set(ch for ch, ch_cnt in cnt.items() if ch_cnt == min_cnt)

# 再次遍历s中的所有字符ch，如果ch不位于哈希集合min_cnt_set中，则可以保留，储存在ans数组中
ans = [ch for ch in s if ch not in min_cnt_set]

# 如果ans的长度为0，说明所有字符均被删除，此时需要输出"empty"
# 否则，则用字符串的join()方法，将ans数组转化为字符串并输出
print("empty" if len(ans) == 0 else "".join(ans))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();

        Map<Character, Integer> cnt = new HashMap<>();
        for (char ch : s.toCharArray()) {
            cnt.put(ch, cnt.getOrDefault(ch, 0) + 1);
        }

        int minCnt = Collections.min(cnt.values());

        Set<Character> minCntSet = new HashSet<>();
        for (Map.Entry<Character, Integer> entry : cnt.entrySet()) {
            if (entry.getValue() == minCnt) {
                minCntSet.add(entry.getKey());
            }
        }

        StringBuilder ans = new StringBuilder();
        for (char ch : s.toCharArray()) {
            if (!minCntSet.contains(ch)) {
                ans.append(ch);
            }
        }

        System.out.println(ans.length() == 0 ? "empty" : ans.toString());
    }
}

C++

“`C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <climits>
using namespace std;

int main() {
string s;
getline(cin, s);

<pre><code>map<char, int> cnt;
for (char ch : s) {
cnt[ch]++;
}

int minCnt = INT_MAX;
for (const auto &entry : cnt) {
minCnt = min(minCnt, entry.second);
}

unordered_set<char> minCntSet;
for (const auto &entry : cnt) {
if (entry.second == minCnt) {
minCntSet.insert(entry.first);
}
}

string ans;
for (char ch : s) {
if (minCntSet.find(ch) == minCntSet.end()) {
ans += ch;
}
}

cout << (ans.empty() ? "empty" : ans) << endl;

return 0;
</code></pre>

}

“`

时空复杂度

时间复杂度：O(N)。仅需一次遍历字符串数组。

空间复杂度：O(1)。无论是哈希表还是列表，长度最多为26，为常数级别空间。

说明

华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。

机试分数越⾼评级越⾼，⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知

关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）