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

0)

 `"01"` `1`
`Returns: 1`
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).
2)

 `"1010"` `2`
`Returns: 2`
3)

 `"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.
4)

 `"10012031001"` `3`
`Returns: 2`

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10801

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14422&pm=10801

K.A.D.R

Testers:

PabloGilberto , ivan_metelsky , maksay

Problem categories:

Dynamic Programming