A. Did We Get Everything Covered?

思路

首先我们要考虑什么样的子串是最难出现的，贪心的想法是：我们总希望剩余的字母数尽量少，也就是每个字符更靠近字符串的末尾，这样可以使得剩余可供选择的字符数量最少，这样就容易出现长度不足n的字符串（显然贪心成立）。所以我们要考虑的是这样的选取被什么所限制，换句话说，什么时候我们必须选取下一个字母？很明显，当k个字母全部出现了之后我们必须进行选择，否则我们就可以选择k个字母中不存在的那一个从而使得答案为“NO”，至于选择，我们每次选择k个字母中最晚出现的一个构造答案。最后进行验证和补全很简单

时间复杂度 O(s.size())即为O(N)

Solution
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
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
using ll = long long;

void solve() {
    int n, k, m;
    cin >> n >> k >> m;
    string s;
    cin >> s;
    unordered_map<char, int> mp;
    string ans = "";
    for (const auto &i : s) {
        mp[i] = 1;
        if (mp.size() == k) {
            ans += i;
            mp.clear();
        }
    }
    if ((int)ans.size() < n) {
        cout << "NO\n";
        for (int i = 0; i < k && ans.size() < n; ++i) {
            if (!mp.count(i + 'a'))
                ans += char('a' + i);
        }
        if (ans.size() < n) {
            ans += string(n - (int)ans.size(), 'a');
        }
        cout << ans << '\n';
    } else {
        cout << "YES\n";
    }
    return;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    // cout << fixed << setprecision(20);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}