LepBroj - Državno
We say that a natural number is beautiful if the distance between any two same digits in it is at least 10. The distance between two digits is equal to the amount of digits between them + 1 (for example, in the number 12342, the distance between the digits '2' is 3).
We are given a number of n digits, and we want to make a beautiful number out of it. In a single move we can erase any digit of the initial number and write any other in its place. What's the smallest amount of moves necessary to get a beautiful number?
InputFrom the first line of the standard input read a natural number n which represents the number of digits of the initial number (1 ≤ n ≤ 10^6). From the next line input the initial number. There are no spaces between digits and a number can have leading zeroes.
OutputIn the first and only line of the standard output, print the smallest amount of moves needed to get a beautiful number out of the given one.
Input:
Output:
Explanation: If we erase the digit 0 on the second position and write a digit 2 instead, and erase the digit 3 ond the seventh position and write a digit 5 instead, we get a beautiful number 02346751. It is possible to get other beautiful numbers but not in a smaller amount of moves.
8
00346731Output:
2Explanation: If we erase the digit 0 on the second position and write a digit 2 instead, and erase the digit 3 ond the seventh position and write a digit 5 instead, we get a beautiful number 02346751. It is possible to get other beautiful numbers but not in a smaller amount of moves.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.