[Google][LintCode] Next Closest Time

Problem: Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, "01:34", "12:09" are valid. "1:34", "12:9" are invalid.

Example:

Input: "19:34"
Output: "19:39"
Explanation:
The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.  
It is not 19:33, because this occurs 23 hours and 59 minutes later.

Input: "23:59"
Output: "22:22"
Explanation:
It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.

Approach: Let's try to find out the next digit for each position in "HH:MM" from right to left. If the next digit is greater than current digit, return directly and keep other digits unchanged.

Here is the steps: (Let's take an example say "17:38")

• Retrieve all four digits from given string and sort them in asscending order,"17:38"->digits[] {'1', '3', '7', '8'}
• Call findNext() from the right most digit to left most digit, which actually try to find next greater digit from digits[](if exist) which is suitable for current position, otherwise return the minimum digit (digits[0]):
• "HH:M#": There is no upperLimit for this position (0-9). Just pick the next different digit in the sequence. In the example above,'8' is already the greatest one, so we change it into the smallest one (digits[0]i.e.'1') and move to next step. ("17:38" -> "17:31")
• "HH:#M": The upperLimit is '5' obviously (max 59 seconds). The next different digit for '3' is '7', which is greater than '5', so we can't take it, hence we take the smallest one digits[0]. ("17:31" -> "17:11")
• "H#:MM": the upperLimit depends on previous digit which is time[0]. If time[0] is '2', then upper limit is '3' (20 - 23) else no upperLimit (0-9). Here we have time[0] as '1', so we can choose any digit we want. The next digit for '7' is '8', so we change it and return the result directly. ("17:11" -> "18:11")
• "#H:MM": the upperLimit is'2' (00 - 23).

Implementation in C#:

        public string NextClosestTime(string time)

{

char[] result = time.ToCharArray();

char[] digits = new char[] {

                                time[0],

                                time[1],

                                time[3],

                                time[4] };

Array.Sort(digits);

result[4] = this.findSuitableDigit(

                            digits,

                            '9',

                            result[4]);

if (result[4] > time[4])

{

return new string(result);

}

result[3] = this.findSuitableDigit(

                            digits,

                            '5',

                            result[3]);

if (result[3] > time[3])

{

return new string(result);

}

result[1] = this.findSuitableDigit(

digits,

result[0] == '2' ? '3' : '9',

result[1]);

if (result[1] > time[1])

{

return new string(result);

}

result[0] = this.findSuitableDigit(

                            digits,

                            '2',

                            result[0]);

return new string(result);

}

private char findSuitableDigit(

char[] digits,

int upperLimit,

char currDigit)

{

if (currDigit == upperLimit)

{

return digits[0];

}

int i = 0;

while (i < digits.Length &&

                digits[i] <= currDigit)

{

++i;

}

if (i == digits.Length)

{

return digits[0];

}

return digits[i] > upperLimit ?

                digits[0] :

                digits[i];

}

Complexity: O(n) (The length is constant)