codeforces 372 Complete the Word(双指针)
题链
题意:给出一个字符串，其中'?'代表这个字符是可变的，要求一个连续的26位长的串，其中每个字母都只出现一次
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int N=5e4+10;
char a[N];
int book[30];
int main()
{while(~scanf("%s",a)){int i=0,j=0,len=strlen(a);int u,v;memset(book,0,sizeof(book));for(j=0;j<len;j++){if(j-i==26) break;if(a[j]=='?') continue;else if(book[a[j]-'A']){while(i<j&&a[i]!=a[j]){if(a[i]=='?'){i++;continue;}else book[a[i]-'A']=0;i++;}if(i!=j){i++;}}else book[a[j]-'A']=1;}if(j-i!=26){puts("-1");continue;}int kk=0;memset(book,0,sizeof(book));for(int k=i;k<j;k++){if(a[k]!='?') book[a[k]-'A']=1;}for(int k=i;k<j;k++){if(a[k]=='?'){for(;kk<26;kk++){if(!book[kk]){a[k]=kk+'A';book[kk]=1;break;}}}}for(int k=0;k<len;k++){if(a[k]=='?'){a[k]='A';}}printf("%s\n",a);}return 0;
}
