영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Christian wants to learn to play the piano but can only manage to play with his index finger right now. Currently, he is practicing hard to learn a piece. A piece is described by a sequence of keys to be pressed in order. For example, the piece abdaa indicates that he should press the keys a, b, d, a, a in order.
However, you notice that he struggles to move his finger quickly between the keys. Curiously, it always takes him exactly one second to move his finger one key to the side but zero seconds to press a key.
To help him, you plan to rearrange the order of the piano keys so that the total time it takes to play the piece is minimized.
For example, if the piece he is trying to learn is abdaa and the piano has the order abd … (the rest of the piano is not shown as it does not affect the answer), it will take a total of 4 seconds to play the piece. The distances when he plays the piece are as follows:
atobtakes one second.btodtakes one second.dtoatakes two seconds.atoatakes zero seconds.
This means that it takes a total of four seconds to play the piece abdaa on a piano with the order abd ….
Write a program that reads a piece and outputs the total time it takes for Christian to play the piece on the piano with the best possible key order.
Input
The first and only line of input contains a string S (1 ≤ |S| ≤ 200), the piece that Christian wants to learn. The piece consists of characters from a-z and contains at most 15 distinct characters.
Output
Print an integer: the number of seconds it takes for Christian to play the piece on a piano with the best possible key order.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 20 | The piece contains at most 8 distinct characters. |
| 2 | 80 | No additional constraints. |
Explanation of sample 2
One possible optimal order of the piano keys is adbc.
예제
예제 1
abdaa
4
예제 2
abdaadbc
7