410589: GYM104059 J Jesting Jabberwocky
Description
As huge card game nerds, Alice and her friends are very hyped about meeting up and trying out the card game everybody seems to talk about these days. Due to a traffic jam, Alice is a bit late to the party and her friends are impatiently waiting for her. They have already distributed all cards and everybody is ready to go, except for Alice. She has just picked up her cards and insists on sorting them by suit first. For that, she repeatedly picks one card from her hand and inserts it somewhere else until her cards are grouped by suit. Her friends are getting increasingly annoyed with Alice and she wants to sort her cards as quickly as possible. How many cards does Alice need to move before they can start playing?
InputThe input consists of:
- One line with a string $$$s$$$ ($$$1\leq|s|\leq 10^5$$$), representing the suits of Alice's cards as they are initially ordered. The string consists of the characters h, d, c, and s (hearts, diamonds, clubs and spades).
Output a single integer, the minimum number of cards Alice has to move in order to sort the cards by suit.
ExamplesInputhccdhcdOutput
2Input
cchhdshcdshdcshOutput
7