== include(page="template/taskheader" task_id="smooth2") ==

Un sir de caractere se numeste _smooth_ daca e format doar din literele mici ale alfabetului englez si, pentru orice prefix al sau, nu exista 2 caractere, din cele care exista in sirul intreg, al caror numar de aparitii in prefix difera prin mai mult de 1. Gasiti numarul minim de caractere ce trebuie inlocuite astfel incat un sir dat sa devina _smooth_!

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 î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_.
 
Dându-se un şir de litere mici ale alfabetului englez, care este numărul minim de caractere ce trebuie înlocuite pentru a transforma şirul într-un şir _smooth_?

h2. Date de intrare

Fişierul de intrare $smooth2.in$ contine un sir de litere mici ale alfabetului englez.

Fişierul de intrare $smooth2.in$ contine un şir de litere mici ale alfabetului englez.

h2. Date de ieşire

În fişierul de ieşire $smooth2.out$ se afla numarul minim de litere ce trebuie inlocuite astfel incat sirul dat sa devina _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 ≤ numarul de litere ≤ 100.000$

* $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.
* 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 |
| jjbjqbqqjbqqjqj | 4 | |

| 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") ==