Un şir de caractere se numeşte _smooth_ dacă:
- Este format doar din literele mici ale alfabetului englez.

- Pentru fiecare prefix al său este adevărat că diferenţa dintre frecvenţa maximă şi frecvenţa minimă a unei litere este cel mult egală cu $1$. În această condiţie sunt luate în considerare *doar* literele care apar cel puţin o dată în şir.

- Pentru fiecare prefix al său este adevărat că diferenţa dintre frecvenţa maximă şi frecvenţa minimă a unei litere este cel mult egală cu $1$. În această condiţie sunt luate în considerare *doar* literele care apar cel puţin o dată *în întregul şir*, indiferent de prefixul examinat.

Spre exemplu, şirurile "abca", "aaaaaaa" şi "baab" sunt _smooth_, în timp ce şirurile "aab" şi "abracadabra" *nu* sunt _smooth_.

În fişierul de ieşire $smooth2.out$ se află numărul minim de litere ce trebuie înlocuite astfel încât sirul dat să devină _smooth_.

h2. Restricţii

h2. Restricţii şi precizări

* $1 ≤ numărul de litere ≤ 100.000$

* Pentru teste în valoare de 10 puncte $1 ≤ numărul de litere ≤ 8$
* Pentru alte teste în valoare de 10 puncte $1 ≤ numarul de litere ≤ 1000$ şi răspunsul e cel mult 2.

* Pentru teste în valoare de *10* puncte $1 ≤ numărul de litere ≤ 8$
* Pentru alte teste în valoare de *10* puncte $1 ≤ numarul de litere ≤ 1000$ şi răspunsul e cel mult 2.
* Numim prefix al unui şir orice subsecvenţă continuă care începe de la prima poziţie a şirului.
* Veţi primi rezultatele evaluării _doar_ pe fişierele de intrare din exemplu. Acestea nu vor afecta scorul problemei, având punctajul asociat 0.

h2. Exemplu
table(example). |_. smooth2.in |_. smooth2.out |_. Explicatie |

| aaba | 1 | Se schimba prima litera, sirul devine {*b*}aba |
| aabaa | 1 | Se schimba a treia litera, sirul devine aa{*a*}aa |
| abccbbcc | 2 | Se schimba a sasea si a saptea litera, sirul devine abccb{*ab*}c |

| aaba | 1 | Se schimbă prima literă, sirul devine {*b*}aba |
| aabaa | 1 | Se schimbă a treia literă, sirul devine aa{*a*}aa |
| abccbbcc | 2 | Se schimbă a şasea si a şaptea literă, şirul devine abccb{*ab*}c |

| jjbjqbqqjbqqjqj | 4 | Sunt suficiente patru schimbări.|
== include(page="template/taskfooter" task_id="smooth2") ==