完美串 - 题解

标签与难度

标签: 贪心, 优先队列, 字符串, 构造, 枚举难度: 1700

题目大意喵~

你好呀，未来的算法大师！本喵今天带来了一道关于字符串排列的有趣问题，喵~

题目是这样子的：给你一个只包含小写字母的字符串 s。你的任务是把 s 里的所有字符重新排列，得到一个新字符串 s'。我们希望这个新字符串 s' 的“完美长度” m 尽可能大。

那么，“完美长度” m 是怎么定义的呢？对于一个字符串 t，如果它所有长度为 m 的子串，都满足一个神奇的性质，那 m 就是一个“完美长度”。这个性质是：对于任意一个长度为 m 的子串，它自己的所有非空子串都是两两不相同的。

听起来有点绕，对吧？别担心，我来帮你分析一下！一个字符串的“所有非空子串都两-两不同”，其实等价于这个字符串本身不包含任何重复的字符。比如说，"abc" 的所有子串 "a", "b", "c", "ab", "bc", "abc" 都是独一无二的。但 "aba" 就不行了，因为它有两个子串 "a"。

所以，题目的要求可以翻译成：我们要找一个最大的整数 m，使得重新排列后的字符串 s' 中，任意一个长度为 m 的连续子串，都由 m 个互不相同的字符组成。

举个栗子：如果 s = "abacaba"，我们可以把它重新排列成 s' = "abacaba" (咦，好像没变)。如果 m=2，我们检查所有长度为2的子串："ab", "ba", "ac", "ca", "ab", "ba"。它们都由不同字符组成，所以 m=2 是一个可行的完美长度。但如果 m=3，子串 "aba" 就出现了重复字符 'a'，所以 m=3 不行。我们的目标就是找到那个最大的 m 和一个对应的 s'。

解题思路分析

喵哈哈，这道题的核心就是把那个复杂的条件“翻译”成我们熟悉的样子，呐！

第一步：理解核心约束

正如我们刚才分析的，s' 的任意长度为 m 的子串都必须由不同字符构成。这意味着，对于字符串 s' 中的任意一个位置 i，从它开始的子串 s'[i], s'[i+1], ..., s'[i+m-1] 里的所有字符都不能相同。

这给我们一个非常重要的启示：如果 s' 中有两个相同的字符，比如 s'[i] == s'[j] 并且 i < j，那么它们之间的距离 j - i 必须至少是 m。为什么呢？如果 j - i < m，那么我们就可以找到一个从 i 之后某个位置开始的长度为 m 的子串，它会同时包含 s'[i] 和 s'[j]，这就违反了“字符互不相同”的规定啦！

所以，问题被我们转化成了一个更清晰的目标： 将原字符串 s 的字符重新排列，得到 s'，使得 s' 中任意两个相同字符之间的最小距离最大化。这个最大化的最小距离，就是我们要找的 m。

第二步：如何找到最大的 m？

既然我们要找一个最大值，一个很自然的想法就是从大到小去尝试，喵~ 我们可以枚举 m 的值，看它是否可行。m 的最大可能值是多少呢？最多也就是字符串中不同字符的种类数，不会超过26。所以我们可以从 m = 26 (或者更精确地说，从字符串 s 中不同字符的数量) 开始，一直往下尝试到 m = 1。我们找到的第一个能够成功构造出 s' 的 m，就是答案！

第三步：如何检查一个 m 是否可行？ (check(m))

现在的问题是，对于一个给定的 m，我们怎么判断是否存在一个合法的排列 s' 呢？这是一个构造问题，通常可以用贪心策略来解决，的说！

我们来模拟一下构造 s' 的过程，从左到右一个一个地放置字符。在第 i 个位置，我们应该放哪个字符呢？为了让构造尽可能成功，我们应该优先使用那些“最麻烦”的字符。什么字符最麻烦呢？当然是数量最多的字符啦！因为它们最容易“挤在一起”，导致违反距离不小于 m 的约束。

所以，我们的贪心策略是： 在每一个位置，从所有当前可用的字符中，选择一个剩余数量最多的来放置。

“当前可用”是什么意思呢？一个字符 c 在位置 i 是“可用”的，需要满足两个条件：

它的库存（剩余数量）大于0。
它没有在 s' 的前 m-1 个位置（也就是 s'[i-1], s'[i-2], ..., s'[i-m+1]）中出现过。这其实就是我们前面推导出的“冷却时间” (cooldown) 的概念：一个字符被使用后，需要“冷却” m-1 个回合，到第 m 个回合才能再次使用。

第四步：实现贪心策略

为了高效地实现这个贪心策略，我们需要两个得力的小助手：

优先队列 (Priority Queue)：用来存放所有“当前可用”的字符。它会自动按照字符的剩余数量排序，让我们每次都能轻松取到数量最多的那个。
一个“冷却”机制：用来管理那些刚刚被使用过，正在“冷却”中的字符。当一个字符在位置 i 被使用后，它要到位置 i+m 才能再次变为“可用”。我们可以用一个数据结构来记录这些信息。一个 vector<vector<pair<int, char>>> 就很棒，cooldown_schedule[j] 存放所有在位置 j 结束冷却、重新变得可用的字符和它们的剩余数量。

整合一下 check(m) 的流程就是：

统计原字符串 s 中每个字符的出现次数。
创建一个优先队列 available_chars_pq 和一个冷却计划表 cooldown_schedule。
把所有出现次数大于0的字符，连同它们的数量，都放进 cooldown_schedule[0]，表示它们在第0个位置就可用了。
开始构建长度为 n 的新字符串 s'，从 i = 0 到 n-1： a. 检查 cooldown_schedule[i]，把所有在当前位置 i 结束冷却的字符放回优先队列 available_chars_pq 中。 b. 如果此时优先队列是空的，说明在当前位置 i 无计可施，没有任何字符可用了！构造失败，这个 m 不可行。 c. 从优先队列中取出数量最多的字符 c。 d. 将 c 放在 s' 的第 i 个位置。 e. 将 c 的数量减一。如果数量还大于0，就把它加入冷却计划，让它在 i+m 位置重新可用，即放入 cooldown_schedule[i+m]。
如果循环顺利完成，说明我们成功构造出了一个合法的 s'，这个 m 是可行的！

这样，我们从大到小枚举 m，一旦 check(m) 成功，就立刻找到了答案，喵~

代码实现

这是本喵根据上面的思路，精心为你准备的代码哦~ 注释超详细的，快来看看吧！

cpp

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

// 用于优先队列的自定义比较结构，让数量多的字符排在前面
struct CharInfo {
    int count;
    char character;

    // 重载小于号，因为C++的priority_queue是最大堆
    bool operator<(const CharInfo& other) const {
        return count < other.count;
    }
};

// 检查给定的完美长度 m 是否可行
// 如果可行，返回构造出的字符串；否则返回空字符串
string check(int m, int n, const map<char, int>& initial_counts) {
    // 优先队列，存放当前所有可用的字符及其数量
    priority_queue<CharInfo> available_chars_pq;

    // 冷却计划表，cooldown_schedule[i] 存储在位置 i 变得可用的字符
    vector<vector<CharInfo>> cooldown_schedule(n + m);

    // 初始时，所有字符在位置 0 都是可用的
    for (auto const& [key, val] : initial_counts) {
        if (val > 0) {
            cooldown_schedule[0].push_back({val, key});
        }
    }

    string result_builder = "";
    result_builder.reserve(n);

    // 从左到右构建字符串
    for (int i = 0; i < n; ++i) {
        // 将在当前位置 i 结束冷却的字符加入优先队列
        for (const auto& info : cooldown_schedule[i]) {
            available_chars_pq.push(info);
        }

        // 如果没有可用的字符，说明无法在当前位置放置任何字符
        // 构造失败，此 m 不可行
        if (available_chars_pq.empty()) {
            return "";
        }

        // 贪心选择：取出数量最多的可用字符
        CharInfo current_char_info = available_chars_pq.top();
        available_chars_pq.pop();

        // 将选中的字符添加到结果字符串中
        result_builder += current_char_info.character;

        // 将该字符的数量减一
        current_char_info.count--;

        // 如果该字符还有剩余，则将其放入冷却计划
        // 它将在 m 个位置之后，即 i + m 的位置，再次可用
        if (current_char_info.count > 0) {
            if (i + m < cooldown_schedule.size()) {
                cooldown_schedule[i + m].push_back(current_char_info);
            }
        }
    }

    // 如果成功构建了长度为 n 的字符串，则返回结果
    return result_builder;
}

void solve() {
    string s;
    cin >> s;
    int n = s.length();

    // 1. 统计字符频率和不同字符的数量
    map<char, int> char_counts;
    for (char c : s) {
        char_counts[c]++;
    }
    int distinct_chars_count = char_counts.size();

    // 2. 从大到小枚举 m
    for (int m = distinct_chars_count; m >= 1; --m) {
        string result = check(m, n, char_counts);
        // 3. 如果找到了一个可行的 m，它就是最大的，直接输出并结束
        if (!result.empty()) {
            cout << m << endl;
            cout << result << endl;
            return;
        }
    }
}

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();

    return 0;
}

复杂度分析

时间复杂度: $O(K \cdot N \log K)$ ，其中 $N$ 是字符串的长度， $K$ 是不同字符的数量。
- 我们从大到小枚举 m，这个外层循环最多执行 $K$ 次 (因为 m 的上界是 $K$ ，且 $K \le 26$ )。
- 在 check(m) 函数中，我们有一个主循环，执行 $N$ 次来构建字符串。
- 在循环的每一步中，我们对优先队列进行操作（push 和 pop）。优先队列中最多有 $K$ 个元素，所以每次操作的时间复杂度是 $O(\log K)$ 。
- 因此，总的时间复杂度是 $O(K \cdot N \log K)$ 。因为 $K$ 是一个很小的常数（最大为26），所以这个算法非常高效，可以看作是接近线性的 $O(N)$ 。
空间复杂度: $O(N + K)$
- 我们需要一个 map 来存储字符计数，空间为 $O(K)$ 。
- 优先队列最多存储 $K$ 个元素，空间为 $O(K)$ 。
- cooldown_schedule 这个向量的大小是 $N+m$ ，并且总共存储了 $N$ 个字符实例，所以空间是 $O(N)$ 。
- 结果字符串 result_builder 的空间也是 $O(N)$ 。
- 所以总的空间复杂度是 $O(N+K)$ 。

知识点总结

这道题真是一次愉快的思维体操呢，喵~ 我们来总结一下学到了什么吧：

问题转化: 能够将题目中看似复杂的定义（子串的子串不同）转化为一个更简洁、更具操作性的模型（相同字符间的最小距离），是解决问题的关键第一步。
贪心算法: 面对构造类问题，贪心是一个非常有力的武器。本题中“优先使用数量最多的可用资源”是一种常见的贪心策略，尤其适用于调度和资源分配类型的问题。
优先队列: 它是实现贪心策略的完美工具！可以帮助我们动态地维护一个有序集合，并快速获取最优选择。
“冷却”机制: 在处理带有“距离”或“时间间隔”约束的问题时，引入一个“冷却”或“延迟”模型是非常有效的。我们可以用队列、数组或向量等数据结构来实现这个机制。
枚举与搜索: 当答案的范围不大且有序时（比如本题的 m），从优到劣进行枚举（或二分搜索答案）是一种简单而可靠的框架。

希望这篇题解能帮到你！继续加油，你一定能成为超厉害的算法大师的，喵~ ❤️

完美串 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​