== include(page="template/taskheader" task_id="smooth2") ==
Poveste şi cerinţă...
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$ ...
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$ ...
Î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.
* 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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. smooth2.in |_. smooth2.out |_. Explicatie |
| 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") ==
