04 | 笔试算法题：凑最长不重复字符串的数目问题

题目

题目描述
定义字符串的”奇怪度”为其最长非重复子串的数量（按起止位置计数）。给定整数 n 和 k，构造长度为 n、仅由小写字母组成的字符串，使其奇怪度恰好为 k。

非重复子串：每个字符出现次数不超过 1 的子串。

样例
输入5 3
输出abaab

分析

• 这题有个很关键的观察：

• 如果字符串只用两种字符，比如 a 和 b
• 那么任意长度 >= 3 的子串一定有重复字符
• 所以这类串的最长非重复子串长度最多是 2

于是问题就变成了：

• 只要串里存在至少一个相邻不同的位置，那么最长非重复子串长度就是 2
• 此时“奇怪度”就等于 相邻不同的二元子串个数
• 也就是相邻位置中 s[i] != s[i+1] 的次数

构造

情况 1：k = n

直接输出全 a：

aaaa...a

因为：

• 没有长度为 2 的非重复子串
• 最长非重复子串长度是 1
• 长度为 1 的子串一共有 n 个
• 所以奇怪度就是 n

情况 2：1 <= k < n

构造：

• 前面放 n-k 个 a
• 后面接一个长度为 k 的交替串，从 b 开始，例如 babab...

即：

a...(n-k个) + babab...

例如 n=5, k=3：

aa + bab = aabab

相邻不同的次数恰好是：

• 前缀最后一个 a 到后缀第一个 b：1 次
• 后缀内部交替：k-1 次

总共正好 k 次。

而整个串只含 a/b 两种字符，所以最长非重复子串长度就是 2，奇怪度正好为 k。

代码

点击查看代码

 #include <bits/stdc++.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, k;cin >> n >> k;// 如果题目不保证有解，可以保底判断if (k < 1 || k > n) {cout << -1 << '\n';return 0;}string s;if (k == n) {s = string(n, 'a');} else {s = string(n - k, 'a');for (int i = 0; i < k; ++i) {s += (i % 2 == 0 ? 'b' : 'a');}}cout << s << '\n';return 0;}