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.
Date de intrare
Fişierul de intrare smooth2.in contine un sir de litere mici ale alfabetului englez.
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.
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 |