| Fişierul intrare/ieşire: | smooth2.in, smooth2.out | Sursă | Algoritmiada 2018 Runda PreOJI |
| Autor | Mihai Calancea | Adăugată de |  Alexandru Petrescu •alexpetrescu |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Smooth2
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?
Date de intrare
Fişierul de intrare smooth2.in contine un şir de litere mici ale alfabetului englez.
Date de ieşire
Î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.
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.
Exemplu
| smooth2.in | smooth2.out | Explicatie |
|---|---|---|
| aaba | 1 | Se schimbă prima literă, sirul devine baba |
| aabaa | 1 | Se schimbă a treia literă, sirul devine aaaaa |
| abccbbcc | 2 | Se schimbă a şasea si a şaptea literă, şirul devine abccbabc |
| jjbjqbqqjbqqjqj | 4 | Sunt suficiente patru schimbări. |
