给定一个由大写字母构成的字符串 $s$。
字符串 $s$ 中的若干个(也可能没有)字符缺失了,缺失的字符用 ?
表示。
现在,请你将字符串进行补全,即将字符串中的每个 ?
字符都替换为一个任意大写字母(A
- Z
)。
要求,补全后的字符串至少包含一个长度为 $26$ 的连续子串,在该子串中,每个大写字母恰好出现一次。
输入格式
共一行,一个字符串 $s$,其中的每个字符都是大写字母(A
- Z
)或问号(?
)。
输出格式
如果不存在合理的补全方案,得到满足条件的完整字符串,则输出 $\-1$。
如果存在合理的补全方案,则输出补全后的字符串。
如果方案不唯一,输出任意合理方案均可。
数据范围
前 $6$ 个测试点满足 $1 \\le |s| \\le 100$。
所有测试点满足 $1 \\le |s| \\le 50000$。
输入样例1:
ABC??FGHIJK???OPQR?TUVWXY?
输出样例1:
ABCDEFGHIJKLMNOPQRZTUVWXYS
输入样例2:
ABCDEFGHIJKLMNOPQRSTUVWXY
输出样例2:
-1
输入样例3:
??????????????????????????
输出样例3:
MNBVCXZLKJHGFDSAQPWOEIRUYT
输入样例4:
AABCDEFGHIJKLMNOPQRSTUVW??M
输出样例4:
-1
思路
滑动窗口,如果一个长度为 $26$ 的窗口中有一个字母大于 $1$ ,那么这个窗口就可以作废了。
代码
删掉了一些考场多写的代码
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
string s;
unordered_map <char,int> mp;
int main () {
cin >> s;
if (s.size () < 26) {
puts ("-1");
return 0;
}
bool f = false;
int i = 0,j = 25;
for (int x = 0;x < 26;x++) mp[s[x]]++;
while (j < s.size ()) {
bool flag = true;
for (int k = i;k <= j;k++) {
if (s[k] == '?') continue;
if (mp[s[k]] > 1) {
flag = false;
break;
}
}
if (!flag) {
mp[s[i]]--,mp[s[j + 1]]++;
i++,j++;
continue;
}
string p;
for (char k = 'A';k <= 'Z';k++) {
if (!mp[k]) p += k;
}
if (p.size () < mp['?']) {
mp[s[i]]--,mp[s[j + 1]]++;
i++,j++;
continue;
}
int t = 0;
string backup = s;
unordered_map <char,int> vis;
for (int k = i;k <= j;k++) {
if (s[k] == '?') s[k] = p[t++];
vis[s[k]]++;
}
bool g = true;
for (char k = 'A';k <= 'Z';k++) {
if (!vis[k]) {
g = false;
break;
}
}
if (!g) {
mp[s[i]]--,mp[s[j + 1]]++;
i++,j++;
s = backup;
continue;
}
f = true;
break;
}
if (!f) {
puts ("-1");
return 0;
}
for (char x : s) {
if (x == '?') cout << 'A';
else cout << x;
}
return 0;
}