Everyone is familiar with the QWERTY keyboard layout:
| Q | W | E | R | T | Y | U | I | O | P |
| A | S | D | F | G | H | J | K | L | |
| Z | X | C | V | B | N | M |
Cosmin is new to the world of computers and technology. He is currently learning to type on a keyboard, by using only his two index fingers. Today, he is practicing his new skill by typing a non-empty sequence of uppercase English letters.
Initially, Cosmin places his left index finger on F and his right index finger on J. At each point in time, he chooses one of his fingers, moves it to the next letter in the sequence, and presses that particular key. The cost of doing so is equal to the Manhattan distance between the old and the new position of his finger.
Your task is to find the minimum total cost of typing the entire sequence.
Input
The first line of input contains the letter sequence.
Output
A single integer: the minimum total cost of typing the entire sequence.
Constraints
- The sequence contains at most 100 letters.
Samples
| Input | Output | Explanation |
|---|---|---|
| FFJJJFJFJFJ | 0 | Cosmin doesn't even need to lift his fingers to type this. |
| QKL | 6 |
|
We can solve the problem using dynamic programming:
Let dp[i][L][R] = the minimum total cost of typing the first i characters, such that we end up with the left finger on the L key and the right finger on R.
Initially, dp[0]['F']['J'] = 0 and dp[everything else] = inf.
Now, assume we are in the state [i][L][R]. There are two ways of having reached this state:
- from [i-1][prevL][R], by moving the left finger from prevL to L
- from [i-1][L][prevR], by moving the right finger from prevR to R
In addition, we know that by reaching [i][L][R], we have just typed the ith character.
As a consequence, either L or R must be equal to s[i].
Finally, we construct the following recursion:
- dp[i][s[i]][prevR] = min(dp[i][s[i]][prevR], dp[i-1][prevL][prevR] + manhattanDist[prevL][s[i]]);
- dp[i][prevL][s[i]] = min(dp[i][prevL][s[i]], dp[i-1][prevL][prevR] + manhattanDist[prevR][s[i]]);
The answer is the minimum value of dp[N][L][R], for any L, R in the alphabet.
