Có thể chứng minh rằng xâu cần tìm chắc chắn có dạng '~abababa...a~'. Vì vậy bài toán của ta đơn giản là tìm xâu con có dạng '~abababa...a~' dài nhất.

Để tìm được xâu như vậy thì ta sẽ xét từng vị trí trên xâu kí tự, giả sử đang xét đến vị trí ~i~, ta duyệt tìm vị trí ~j~ xa nhất sao cho xâu con từ ~i~ đến ~j~ vẫn thỏa mãn là xâu có dạng '~abababa...a~', cập nhật kết quả và ta sẽ nhảy ~i~ đến vị trí ~j~ đề không bị xét lại các xâu con của xâu từ ~i~ đến ~j~.

Độ phức tạp: ~O(n)~.

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

const int N = 1e6 + 5;
int n, mx, dp[N];
string s;

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> s;

    for1(i,2,n - 1) if (s[i] == 'a' && s[i - 1] == 'b' && s[i - 2] == 'a') {
        dp[i] = dp[i - 2] + 1;
        if (dp[i] > dp[mx]) mx = i;
    }

    cout << 'a';
    for1(i,1,dp[mx]) cout << "ba";


}