426. Честный дележ

Вам дана строка $s$, которую вы купили в качестве угощения к чаю. Теперь, прежде чем позвать гостей, нужно определить, на сколько гостей можно разделить $s$.

Формально разделением строки $s$ называется её разбиение на подстроки $s_1,\ s_2,\ \ldots, s_k$ таким образом, что $s_1 + s_2 + \ldots + s_k = s$, подстроки совпадают как мультимножества символов. Например, строку $\text{"ababbaab"}$ можно разделить как на $[\text{ "ab" }, \text{"ab"}, \text{"ba"}, \text{"ab"}]$, так и на $[\text{"abab"}, \text{"baab"}]$.

Вы хотите найти честное разделение строки $s$ на максимальное число подстрок, чтобы определить, сколько гостей можно позвать на чай.

В первой строке записана непустая строка $s$, состоящая из строчных букв английского алфавита. Длина строки $s$ не превосходит $5\cdot10^5$ символов.

Выведите одно число — максимально возможное количество подстрок, на которое можно разделить строку $s$.

Первый тест соответствует строке ababbaab, описанной в условии.

Во втором тесте нельзя разбить строку на больше, чем 1 подстроку, так как в ней есть уникальный символ r.