AmoebaCode | Topcoder Archive

Problem Statement

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.

Definition

Class:: AmoebaCode
Method:: find
Parameters:: String, int
Returns:: int
Method signature:: int find(String code, int K)
(be sure your method is public)

Constraints

K will be between 1 and 7, inclusive.
code will contain between K+1 and 50 characters, inclusive.
Each character of code will be a digit between 0 and K, inclusive.

Examples

```
"01"
```
```
1
```
```
Returns: 1
```
```
"1001"
```
```
2
```
```
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).
```
"1010"
```
```
2
```
```
Returns: 2
```
```
"01001"
```
```
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.
```
"10012031001"
```
```
3
```
```
Returns: 2
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.