Hướng dẫn giải

Subtask 1 (40%): \(N \le 10^2\)

Xét mọi xâu con liên tiếp của xâu \(s\), dùng vòng lặp for để đếm xem mỗi ký tự trong xâu con đó xuất hiện bao nhiêu lần và tính chênh lệch của ký tự xuất hiện nhiều nhất và ít nhất.

Độ phức tạp: \(Ο(N^3)\).

Subtask 2 (30%): \(N \le 10^5\)

Gọi \(cnt[c][l..r]\) là số kí tự \(c\) trên \(s[l..r]\)

Gọi \(diff[c][d][l..r] = cnt[c][l..r] - cnt[d][l..r]\) là chênh lệch giữa số kí tự \(c\) và \(d\) trên \(s[l..r]\)

Gọi \(cmin\) và \(cmax\) là kí tự xuất hiện ít nhất và nhiếu nhất trên \(s[l..r]\) \(\implies ans = max(diff[cmax][cmin][l..r])\) với \(1 \le l \le r \le n\)

Nhận xét: \(diff[c][d][l..r] \le diff[cmax][cmin][l..r]\) với mọi \(c, d\)

\(\implies ans = max\{diff[c][d][l..r]\}\) với \('a' \le c, d \le 'z', 1 \le l \le r \le n\)

Đặt \(pref[c][i]\) là số kí tự \(c\) trên \(s[1..i]\) (mảng cộng dồn) \(\implies cnt[c][l..r] = pref[c][r] - pref[c][l - 1]\)

\(\implies ans = max\{pref[c][r] - pref[c][l - 1] - (pref[d][r] - pref[d][l - 1])\} = max\{pref[c][r] - pref[d][r] - (pref[c][l - 1] - pref[d][l - 1])\}\)

Đặt \(minpref[r] = min\{pref[c][l - 1] - pref[d][l - 1]\}\) với \(l \le r\), \(r\) cố định

\(\implies ans = max\{pref[c][r] - pref[d][r] - mỉnpref[r]\}\)

Vậy ta sẽ duyệt \(c, d, r\) và dùng \(minpref[r - 1]\) để cập nhật \(minpref[r]\)

Tuy nhiên, ta cần đảm bảo \(cnt[c][l..r], cnt[d][l..r] > 0\). Ta có thể sử dụng two-pointers, duyệt \(r\) và tăng dần \(l\) sao cho thỏa mãn điều kiện này và chỉ cập nhật \(minpref[r]\) khi \(l\) tăng

Độ phức tạp: \(Ο(N * 26^2)\).

Subtask 3 (30%): \(N \le 10^6\)

Ta cần giảm ĐPT xuống \(O(N * 26)\). Ta sẽ duyệt \(d, r\), two-pointers \(l\) và tìm mối liên hệ giữa \(c\) và \(l, r\)

Ta coi \(d\) là \(cmin\), \(c\) là \(cmax\) và tìm chênh lệch tối đa tạo ra bởi \(c, d\) để tìm kết quả

Nhận xét: Trong xâu con tối ưu (xâu con ngắn nhất có chênh lệch lớn nhất) sẽ chỉ xảy ra các trường hợp:

1. \(s[cmin..cmax] \implies s[d..c]\)
2. \(s[cmax..cmax] \implies s[c..c]\)
3. \(s[cmax..cmin] \implies s[c..d]\)

Không thể xảy ra trường hợp \(s[cmin..cmin]\) vì khi đó ta có thể xóa ít nhất 1 kí tự ở đầu/cuối để giảm \(cnt[cmin]\) nhằm tăng chênh lệch

Để dễ hình dung, đặt \(prefl = pref[c][l - 1] - pref[d][l - 1]\) và \(prefr = pref[c][r] - pref[d][r]\)

1. TH1: \(s[r] \ne d\) \(\implies s[r] = c\)

   • \(\implies prefr = pref[s[r]][r] - pref[d][r]\) cố định theo \(d, r\) và \(prefl = pref[s[r]][l - 1] - pref[d][l - 1]\)

   • TH1a: \(s[l] = d\) \(\implies prefl = pref[s[r]][l - 1] - pref[s[l]][l - 1]\)

     • Lúc này \(prefl\) phụ thuộc vào \(r\) nên để tìm \(prefl\) ta cần duyệt mọi \(r > l\) thỏa mãn \(cnt[d][l..r] > 0\)
     • Tuy nhiên, ta nhận thấy \(s[r]\) chỉ có thể nằm trong \(26\) kí tự từ \('a'\) đến \('z'\). Do đó, thay vì duyệt \(r\), ta có thể duyệt \(c\) từ \('a'\) đến \('z'\) và cập nhật \(min[c] = min(min[c], pref[c][l - 1] - pref[s[l]][l - 1])\) với \(l\) thỏa mãn \(s[l] = d\)
     • Vì số trường hợp \(l, d\) thỏa mãn \(s[l] = d\) là \(n\) nên độ phức tạp vẫn là \(O(N * 26)\) mà không phải \(O(N * 26^2)\)

   • TH1b: \(s[l] \ne d \implies s[l] = c\) \(\implies prefl = pref[s[l]][l - 1] - pref[d][l - 1] = pref[s[r]][l - 1] -pref[d][l - 1]\)

     • Lúc này \(prefl\) không phụ thuộc \(r\), nhưng \(prefr\) chỉ kết hợp được với \(prefl\) để cập nhật vào \(ans\) khi \(s[r] = s[l]\) nên ta sẽ cập nhật \(prefl\) vào \(min1\): \(min1[s[l]] = min(min1[s[l]], pref[s[l]][l - 1] - pref[d][l - 1])\)
   • Vậy khi \(s[r] \ne d\) thì ta cập nhật \(ans = min(ans, prefr - min(min[s[r]], min1[s[r]])\)

2. TH2: \(s[r] = d\) \(\implies s[l] = c\) \(\implies prefl = pref[s[l]][l - 1] - pref[d][l - 1], prefr = pref[s[l]][r] - pref[d][r]\)

   • Lúc này \(prefl\) không phụ thuộc \(r\) nhưng \(prefr\) lại phụ thuộc \(s[l]\) hoặc \(c\)
   • Ta có thể cập nhật \(prefl\) vào \(min1\) (tương tự TH1b) và duyệt \(c\) để thử tất cả \(prefr\) (vì số trường hợp \(r, d\) thỏa mãn \(s[r] = d\) là \(n\) nên ĐPT vẫn là \(O(N * 26)\))

Độ phức tạp \(Ο(N * 26)\).

Code tham khảo

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

const int maxn = 1e6 + 7;
const int inf = 1e9 + 7;

int n, ans = 0;
int s[maxn] = {0};
int pref[26][maxn] = {0};

void program() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        s[i] = (int)(c - 'a');
    }

    for (int i = 0; i < 26; i++) {
        for (int j = 1; j <= n; j++) pref[i][j] = pref[i][j - 1] + (s[j] == i);
    }

    for (int d = 0; d < 26; d++) {
        vector<int> mn(26, inf), mn1(26, inf);
        for (int l = 0, r = 1; r <= n; r++) {
            while (l <= r && pref[d][r] - pref[d][l - 1] > 0) {
                mn1[s[l]] = min(mn1[s[l]], pref[s[l]][l - 1] - pref[d][l - 1]);
                if (s[l] == d) {
                    for (int c = 0; c < 26; c++) mn[c] = min(mn[c], pref[c][l - 1] - pref[s[l]][l - 1]);
                }
                l++;
            }

            if (s[r] != d) ans = max(ans, pref[s[r]][r] - pref[d][r] - min(mn[s[r]], mn1[s[r]]));
            else for (int c = 0; c < 26; c++) ans = max(ans, pref[c][r] - pref[d][r] - mn1[c]);
        }
    }

    cout << ans <<endl;
}


int main() {
    /*#define taskname "chenhlech"
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
    */
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    program();

}