Различные буквы

$f(x)$ — количество различных букв в строке $x$. Разбейте строку $s$ из строчных латинских букв на две непустые строки $a$ и $b$ ($a + b = s$) так, чтобы $f(a) + f(b)$ было максимальным. Найдите это максимальное значение.

В первой строке $n$ ($2 \le n \le 2 \cdot 10^5$). Во второй — строка $s$ из $$ строчных латинских букв.

Одно число — наибольшее значение $f(a) + f(b)$.

Пересчёт обеих частей для каждой точки разреза — $O(n^2)$. Вместо этого посчитайте $L_i$ — число различных букв среди первых $i$ (префикс) и $$ — число различных букв с -й до конца (суффикс). Оба массива считаются за один проход, ответ — .