# 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.  ```

Remember there is no limit on how many times a digit can be reused. so from  1, 9, 3, the digit 9 is used twice to form 19:39, and 4 is never being used to get the output.

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 the next day's time since it is smaller than the input time numerically.```

Intuition and Algorithm

• Convert the time in minutes of the day. Get the `hours` and `minutes` from the input time. Then calculate `currentTimeInMinutes = (60 * hours) + minutes.`
• Now simulate the clock going forward by one minute. Each time it moves forward, if all the digits are allowed, then return the current time.
• The natural way to represent the time is as an integer `t` in the range `0 <= t < 24 * 60`. Then the hours are `t / 60`, the minutes are `t % 60`, and each digit of the hours and minutes can be found by `hours / 10, hours % 10` etc.
```class NextClosestTimeSolution {

public String nextClosestTime(String time) {
int hours = Integer.parseInt(time.substring(0, 2));
int minutes = Integer.parseInt(time.substring(3));
int currentTimeInMinutes = 60 * hours + minutes;
Set<Integer> allowed = new HashSet<>();
for (char c : time.toCharArray()) {
if (c != ':') {
}
}

while (true) {
currentTimeInMinutes = (currentTimeInMinutes + 1) % (24 * 60);
int[] digits = new int[]{
currentTimeInMinutes / 60 / 10,
currentTimeInMinutes / 60 % 10,
currentTimeInMinutes % 60 / 10,
currentTimeInMinutes % 60 % 10
};

if (isValid(allowed, digits)) {
StringBuffer buffer = new StringBuffer();
buffer.append(digits).append(digits);
buffer.append(":");
buffer.append(digits).append(digits);
return buffer.toString();
}
}
}

private boolean isValid(Set<Integer> allowed, int[] digits) {
for (int d : digits) {
if (!allowed.contains(d)) {
return false;
}
}
return true;
}
}

public class NextClosestTime {
public static void main(String[] args) {
String time = "23:59";
NextClosestTimeSolution nextClosestTimeSolution = new NextClosestTimeSolution();
System.out.println(nextClosestTimeSolution.nextClosestTime(time));
}
}
```

Complexity Analysis

• Time Complexity: `O(1)`. We try up to 24 * 60 possible times until we find the correct time.
• Space Complexity: `O(1)`.

Categories: String