最少字符串操作次数

问题描述

小U得到一个只包含小写字母的字符串 S 。她可以执行如下操作：每次选择字符串中两个相同的字符删除，然后在字符串未尾添加一个任意的小写字母。小U想知道，最少需要多少次操作才能使得字符串中的所有字母都不相同？

解题思路

要使每个字符的出现次数唯一，我们可以分三步处理：

  1. 统计字符频率和未使用字符：遍历字符串，统计每个字符出现的次数，并记录未在字符串中出现的字符（从 a 到 z 共 26 个）。
  2. 优先替换操作：对于频率大于 1 的字符，优先使用未使用的字符进行替换。每次替换操作，可以将两个相同的字符替换为一个新字符，这样可以同时减少重复字符的数量和引入新的字符。
  3. 删除多余字符：如果没有未使用的字符可供替换，或者字符频率仍然大于 1，则需要通过同字符+2 -1的操作，相当于删除一个字符来减少重复字符。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;

int solution(const string& S)
{
    unordered_map<char, int> cnt; // 字符以及计数
    unordered_set<char> unc; // 出现的唯一字符集

    for (char c : S)
    {
        cnt[c]++;
        unc.insert(c);
    }

    int left = 26 - unc.size(); // 未使用的字符数
    int op = 0; // 操作数

    for (auto &k : cnt)
    {
        while (k.second > 1 && left > 0) // 优先使用未使用的字符
        {
            op++;
            k.second -= 2;
            left--;
        }
        if (k.second == 0) // 如果刚好用完，归为未使用的字符数
            left++;
    }

    for (auto &k : cnt)
        if (k.second > 1)
            op += (k.second - 1); // 剩余的字符需要的操作数为字符数减一

    return op;
}

int main()
{
    cout << (solution("abab") == 2) << endl;
    cout << (solution("aaaa") == 2) << endl;
    cout << (solution("abcabc") == 3) << endl;
}

代码解析

  • 统计：
    • 使用 unordered_map cnt 统计每个字符的出现次数。
    • 使用 unordered_set unc 记录已使用的字符，计算未使用的字符数量 left。
  • 替换：
    • 遍历每个字符的频率，在有未使用字符的情况下，优先进行替换操作。
    • 每次替换操作减少频率 2，操作次数加 1，未使用字符数量减 1。
  • 删除：
    • 对于仍然频率大于 1 的字符，进行-2 +1的操作，相当于删除一个的操作。
    • 每删除一个字符，操作次数加 1。

知识点总结

  • 哈希表的应用：利用 unordered_map 和 unordered_set 高效统计字符频率和管理字符集合。
  • 贪心算法：优先选择能够最大程度减少重复的操作，即先进行替换，再考虑删除。
  • 字符处理技巧：熟悉字符串及字符集的处理，计算未使用字符的方法。

时间复杂度

  • 统计字符频率：遍历字符串一次，时间复杂度为 $O(n)$ ，其中 $n$ 是字符串的长度。
  • 处理字符频率：在最坏情况下，遍历所有 26 个小写字母的字符频率，时间复杂度为 $O(26)$ ，即常数时间 $O(1)$ 。
  • 总时间复杂度：由于主要操作是对字符串的遍历，因此总体时间复杂度为 $O(n)$ 。

空间复杂度

  • 存储字符频率和未使用字符：使用了两个哈希表（ unordered_map 和 unordered_set ），它们分别存储字符频率和未出现的字符集合。由于字符集固定为 26 个小写字母，空间复杂度是常数 $O(1)$ 。
  • 总空间复杂度：由于字符频率的存储和未使用字符的集合是固定大小的，因此空间复杂度为 $O(1)$ 。

总结

通过分步处理的思路，可以得出最小的操作次数，使每个字符的出现次数唯一。核心是优先使用未使用的字符进行替换操作，从而最大程度地减少删除操作，再得出剩余的字符需要的操作数的公式。哈希表（ unordered_map 和 unordered_set ）在这个问题中可以简化代码，高效地管理字符的频率和未使用字符集合。贪心策略保证了每次操作能够尽可能最大化地减少重复字符。