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 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!
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 |