平衡字符串Plus

问题描述

给定一个字符串，字符串中包括26个大写字母和特殊字符'?'，特殊字符'?'可以代表任何一个大写字母。
是否存在一个位置连续的且由26个大写字母组成的子串，在这个子串中每个字母出现且仅出现一次，如果存在，请输出从左侧算起的第一个出现的符合要求的子串，并且要求，如果有多组解同时符合位置最靠左，则输出字典序最小的那个解；如果不存在，输出-1。

说明：字典序先按照第一个字母，以 A、B、C ...... Z 的顺序排列；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，SIGH 和 SIGHT），那么把短者排在前。例如
AB??EFGHIJKLMNOPQRSTUVWXYZ 
 
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABDCEFGHIJKLMNOPQRSTUVWXYZ
上面两种填法，都可以构成26个字母，但是我们要求字典序最小，只能取前者。
注意，题目要求的是第一个出现的，字典序最小的！

Input

输入只有一行，一个符合题目描述的字符串。

Output

输出只有一行，如果存在这样的子串，请输出，否则输出-1

Sample

Input: 
ABC??FGHIJK???OPQR?TUVWXY?
Output: 
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Input: 
AABCDEFGHIJKLMNOPQRSTUVW??M
Output: 
-1

数据范围

数据点	字符串长度
1, 2, 3	10
4, 5, 6	104
7, 8, 9, 10	106

Limitation

Time limit		1000 ms
Memory limit	65536 kb

解题思路

滑动窗口问题，窗口内26个字符，不断向右滑动；
每次对窗口内字符串判断，先记录26个字母的频率，若有其中一个字母频率>1，则这个窗口一定不行，及时终止；若有字母的频率为0，则一定出现了’?’，记下这个字母；26个字符全扫一遍后，将’?’按字母表顺序全部替换为字母，返回字符串。
不断滑动窗口，直至出现第一个符合情况的字符串，按要求输出。

这样暴力求解，本来是想骗分的，没想到真的AC了……

源代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int getN(char a) {
	if (a >= 65 && a <= 90)
		return a - 64;//标记A~Z：1~26
	else
		return 0;//标记?：0
}

string solve1(string s) {
	int count[27] = { 0 };
	for (int i = 0; i < s.size(); i++)
		count[getN(s[i])]++;
	int c0 = 0;
	int temp[27];
	for (int i = 1; i < 27; i++) {
		if (count[i] > 1) {
			string t = "-1";
			return t;
			break;
		}
		if (count[i] == 0) {
			temp[c0] = i;
			c0++;
		}
	}
	int c2 = 0;
	string res = s;
	for (int i = 0; i < res.size(); i++) {
		if (res[i] == '?') {
			char cha = temp[c2] + 64;
			c2++;
			res[i] = cha;
		}
	}
	return res;
}

string solve2(string s) {
	int size = s.size();
	for (int i = 25; i < size; i++) {
		string c = s.substr(i - 25, 26);
		string res = solve1(c);
		if (res == "-1")
			continue;
		if (res.size() == 26) {
			return res;
			break;
		}
	}
	return "-1";
}

int main() {
	string s;
	cin >> s;
	cout << solve2(s) << endl;

	return 0;
}