Turli harflar

$f(x)$ — $x$ satrdagi turli harflar soni. Kichik lotin harflaridan iborat $s$ satrni ikkita bo'sh bo'lmagan $a$ va $b$ satrga bo'ling ($a + b = s$), shunda $f(a) + f(b)$ eng katta bo'lsin. Shu eng katta qiymatni toping.

Birinchi qatorda $n$ ($2 \le n \le 2 \cdot 10^5$). Ikkinchi qatorda $n$ ta kichik lotin harfidan iborat $s$ satri.

Bitta son — $f(a) + f(b)$ ning eng katta qiymati.

Har bir bo'linish nuqtasi uchun ikkala qismni qaytadan sanash $O(n^2)$. Buning o'rniga $L_i$ — birinchi $i$ ta harfdagi turli harflar soni (prefiks) va $R_i$ — $i$-dan oxirigacha turli harflar soni (suffiks). Ikkalasi bitta o'tishda hisoblanadi, javob — $\max L_i + R_{i+1}$.

Birinchi misolda abc + abcd: $3 + 4 = 7$.

Manba: Codeforces, 1791D-masala.