Little Romeo likes cosmic amoebas a lot. Recently he found an ancient box, and he believes that there is an amoeba inside it. Unfortunately, the box is protected by a combination lock which contains a row of digits, each between 0 and K, inclusive. The initial combination, from left to right, is given in the String code. Romeo thinks that the lock will open if he replaces each 0 digit with some digit between 1 and K, inclusive, such that the minimal distance between any pair of equal digits is as big as possible. The distance between two numbers in positions A and B, respectively, is |A-B|. Return the maximal possible minimal distance that can be achieved.
Examples | | 0) | | | | | | 1) | | | | | Returns: 1 | There are only four possible ways to replace the '0's here:
1121
1211
1111
1221
In each of these combinations, the shortest distance between two equal digits is between consecutive equal digits (a distance of 1). |
|
| | 2) | | | | | | 3) | | | | | Returns: 3 | | One possible combination is "31231". There are two pairs of equal digits here. The distance between the two '3's is 3, and the distance between the two '1's is 3. |
|
| | 4) | | | | CAN ANYONE SUGGEST ME AN EFFICIENT AND EASY TO IMPLY ALGORITHM TO SOLVE THIS PROBLEM...... |
|
Полный текст и комментарии »
