piyushgolani's blog

By piyushgolani, 13 years ago, In English
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)
    
"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
CAN ANYONE SUGGEST ME AN EFFICIENT AND EASY TO IMPLY ALGORITHM TO SOLVE THIS PROBLEM......

Full text and comments »

  • Vote: I like it
  • -12
  • Vote: I do not like it