Jesting Jabberwocky

Interview

Time limit2sMemory limit1024 MB

Summary

Given a string of card suits, find the fewest cards to move so that every suit ends up grouped together.

Level: Medium4 of 10
Topics: String, Dynamic programming, Brute force
Solved: No attempts yet

Problem

Figure J.1: In Sample 1, Alice has to move at least two cards to sort her hand.

The famous card game manufacturer Greatest Cards Production Company (GCPC) has just created the brand new card game Jabberwocky. In this game, everyone gets the same amount of cards (which might be quite a lot), and each card belongs to one of four different suits: hearts, diamonds, clubs, or spades.

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. To do 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?

Input

The 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

Output a single integer, the minimum number of cards Alice has to move in order to sort the cards by suit.

Examples2

Example 1
Input
```
hccdhcd
```
Expected output
```
2
```
Example 2
Input
```
cchhdshcdshdcsh
```
Expected output
```
7
```