贪心加哈希

双指针枚举两个端点

如果不等就将较小的放到队列

如果相等，就用哈希二分出第一个不一样的点（当然这个可以用倍增实现），然后选择那个不一样的最小的一端放入

然后就做完了

code :

#include <bits/stdc++.h>
using namespace std;

bool mlest;

double tlest, tleed;

inline int R() {
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}

void W(int x) {
	if(x < 0) {
		x = -x;
		putchar('-');
	}
	if(x > 9) W(x/10);
	putchar(x%10+'0');
}

const int N = 5e5 + 10;

const int B = 13331;

int n;

char a[N];

unsigned long long p[N], pre[N], suf[N];

void read() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
}

void init() {
	p[0] = 1;
	for(int i = 1;i <= n; i++){
		p[i] = p[i-1] * B;
		pre[i] = pre[i-1] * B + a[i] - 'a' + 1;
		suf[i] = suf[i-1] * B + a[n - i + 1] - 'a' + 1;
	}
}

bool ok(int l1,int r1,int l2,int r2,int len){
	return pre[r1] - pre[l1-1] * p[len] == suf[n-l2+1] - suf[n-r2] * p[len];
}

bool check(int L,int R) {
	int l = 1, r = R - L + 1, ans = 0;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(ok(L,L+mid-1,R-mid+1,R,mid)){
			ans = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	ans++;
	return a[L+ans-1] < a[R-ans+1];
}

void compute() {
	int l = 1, r = n;
	while(l <= r) {
		if(a[l] < a[r]) {
			cout << a[l++]; 
		} else if(a[r] < a[l]) {
			cout << a[r--];
		} else {
			if(check(l,r)) {
				cout << a[l++];
			} else {
				cout << a[r--];
			}
		}
	}
}

void clear() {

}

void run() {
	read();
	init();
	compute();
	clear();
}

bool mleed;

void wa() {
	cout << "\n" << tleed-tlest << "ms\n" << (&mleed-&mlest-1)/1024.0/1024.0<<"MB\n";
}

void fre(string s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

int main() {
//	fre("a");
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	run();
	return 0;
}