Revizia anterioară Revizia următoare
| 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 şir.
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
- 1 ≤ numarul de litere ≤ 100.000
Exemplu
| smooth2.in | smooth2.out | Explicatie |
|---|---|---|
| aaba | 1 | Se schimba prima litera, sirul devine baba |
| aabaa | 1 | Se schimba a treia litera, sirul devine aaaaa |
| abccbbcc | 2 | Se schimba a sasea si a saptea litera, sirul devine abccbabc |
| jjbjqbqqjbqqjqj | 4 | Sunt necesare 4 modificari de litere |
