CSES - Datatähti 2018 alku - Merkkijono
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Uolevilla on merkkijono, joka muodostuu merkeistä A–Z.

Jokaisella siirrolla Uolevi etsii merkkijonosta ensimmäisen merkin, jonka vieressä on toinen sama merkki. Tämän jälkeen hän poistaa siitä merkistä alkaen mahdollisimman pitkän samasta merkistä koostuvan pätkän.

Lopulta merkkijonosta ei voi poistaa enää mitään pätkää. Tehtäväsi on selvittää, millainen merkkijono on silloin.

Syöte

Syötteen ainoalla rivillä on merkkijono, jossa on 1–1000 merkkiä.

Tuloste

Tulosta lopullinen merkkijono siirtojen jälkeen.

Esimerkki 1

Syöte:
CAACCB

Tuloste:
B

Selitys: Uolevi poistaa ensin pätkän AA, jolloin merkkijonosta tulee CCCB. Sitten hän poistaa pätkän CCC, jolloin merkkijonosta tulee B.

Esimerkki 2

Syöte:
ABCDDCBA

Tuloste:


Arvostelu

Koodiasi testataan joukolla merkkijonoja. Saat tehtävästä 100 pistettä, jos koodi toimii oikein kaikissa tapauksissa.