为了删除掉字符串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++

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <climits>
using namespace std;

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

    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;
}

时空复杂度

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

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