Submission #1982071

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<string,int> P;
typedef pair<P,P> P2;
const ll INF=100000000000000001;

int t[26][200001]={};
int ls;
int reg(int pos1,int t2){
	int ub=ls,lb=pos1;
	int k=t[t2][pos1];
	if(t[t2][ub]==k)return pos1;
	while(ub-lb>1){
		int mid=(ub+lb)/2;
		if(t[t2][mid]>k){
			ub=mid;
		}else{
			lb=mid;
		}
	}
	return ub;
}
int main() {
	string s;
	cin>>s;
	ls=s.length();

	for(int i=1;i<ls+1;++i){
		int k=(int)s[i-1]-97;
		for(int j=0;j<26;++j)t[j][i]=t[j][i-1];
//		cout<<k<<endl;;
		t[k][i]++;
	}
//	cout<<"here";

	queue<P> que;
	for(int i=0;i<26;++i){
		string chr="a";
		chr[0]=((char)(97+i));
		que.push(P(chr,0));
	}

	while(!que.empty()){
		P p1=que.front();que.pop();
		string s1=p1.first;
		int pos=p1.second;
		int ls1=s1.length();
		int t1=(int)s1[ls1-1]-97;
		int pos2=reg(pos,t1);
		if(pos2==pos){
			cout<<s1<<endl;
			return 0;
		}else{
			for(int i=0;i<26;++i){
				char chr=(char)(97+i);
				string s2=s1+chr;
				que.push(P(s2,pos2));
			}
		}
//		cout<<s1<<endl;
	}


	return 0;
}

Submission Info

Judge Result