Fişierul intrare/ieşire:smooth2.in, smooth2.outSursăAlgoritmiada 2018 Runda PreOJI
AutorMihai CalanceaAdăugată dealexpetrescuAlexandru Petrescu alexpetrescu
Timp execuţie pe test0.25 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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.insmooth2.outExplicatie
aaba1Se schimbă prima literă, sirul devine baba
aabaa1Se schimbă a treia literă, sirul devine aaaaa
abccbbcc2Se schimbă a şasea si a şaptea literă, şirul devine abccbabc
jjbjqbqqjbqqjqj4Sunt suficiente patru schimbări.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?