# 681. Next Closest Time

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 all valid. "1:34", "12:9" are all invalid.

Example 1:

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.
Example 2:

Input: "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.

## Complexity

Worst Time: O(N2)
O(N)

## Code

``````class Solution {
public String nextClosestTime(String time) {
char[] digits = new char[]{time.charAt(0), time.charAt(1), time.charAt(3), time.charAt(4)};
char[] sortedDigits = digits.clone();
Arrays.sort(sortedDigits);
int i = digits.length - 1;
for(; i >= 0; i--){
int j = 0;
while(j < sortedDigits.length && sortedDigits[j] <= digits[i]) j++;;
if(j < sortedDigits.length){
char tmp = digits[i];
digits[i] = sortedDigits[j];
int hour = (digits[0] - '0') * 10 + (digits[1] - '0');
int minute = (digits[2] - '0') * 10 + (digits[3] - '0');
if(hour <= 24 && minute <= 60)
break;
digits[i] = tmp;
}
}
for(int k = i + 1; k < digits.length; k++){
digits[k] = sortedDigits[0];
}

StringBuilder sb = new StringBuilder();
sb.append(digits[0]).append(digits[1]).append(":").append(digits[2]).append(digits[3]);
return sb.toString();
}
}
``````