CSES - Alijono
  • Time limit: 4.00 s
  • Memory limit: 128 MB
Uolevi ja Maija pelaavat seuraavanlaista peliä:

Ensin Uolevi valitsee merkkijonon, jossa on $n$ merkkiä. Sitten Maija valitsee toisen merkkijonon, jossa on $m$ merkkiä. Maijan merkkijonon tulee olla sellainen, että se ei esiinny alijonona Uolevin merkkijonossa. Molemmissa merkkijonoissa merkistö on A–Z.

Maijan pistemäärä pelistä on $m$, ja pelissä on tavoitteena saada mahdollisimman pieni pistemäärä. Tehtäväsi on selvittää pienin pistemäärä, jonka Maija voi saavuttaa.

Merkkijono Y on merkkijono X:n alijono, jos Y saadaan X:stä poistamalla merkkejä ja säilyttämällä jäljelle jäävien merkkien järjestys. Myös X on itsensä alijono. Esimerkiksi merkkijonon AYBABTU alijonoja ovat AAT, BABT sekä AYABU.

Syöte

Syötteen ainoalla rivillä on Uolevin antama merkkijono, jossa on $n$ merkkiä.

Tuloste

Ohjelmasi tulee tulostaa pienin mahdollinen pistemäärä $m$, jonka Maija voi saavuttaa.

Rajat
  • $1 \le n \le 10^5$
Esimerkki

Syöte:
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Tuloste:
2

Selitys: Esimerkiksi merkkijono AA ei ole Uolevin merkkijonon alijono.