# 681. Next Closest Time

## Description

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: time = "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: time = "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.


Constraints:

• time.length == 5
• time is a valid time in the form "HH:MM".
• 0 <= HH < 24
• 0 <= MM < 60

## Solutions

• class Solution {
private int t;
private int d;
private String ans;
private Set<Character> s;

public String nextClosestTime(String time) {
t = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3));
d = Integer.MAX_VALUE;
s = new HashSet<>();
char mi = 'z';
for (char c : time.toCharArray()) {
if (c != ':') {
s.add(c);
if (c < mi) {
mi = c;
}
}
}
ans = null;
dfs("");
if (ans == null) {
ans = "" + mi + mi + ":" + mi + mi;
}
return ans;
}

private void dfs(String curr) {
if (curr.length() == 4) {
if (!check(curr)) {
return;
}
int p
= Integer.parseInt(curr.substring(0, 2)) * 60 + Integer.parseInt(curr.substring(2));
if (p > t && p - t < d) {
d = p - t;
ans = curr.substring(0, 2) + ":" + curr.substring(2);
}
return;
}
for (char c : s) {
dfs(curr + c);
}
}

private boolean check(String t) {
int h = Integer.parseInt(t.substring(0, 2));
int m = Integer.parseInt(t.substring(2));
return 0 <= h && h < 24 && 0 <= m && m < 60;
}
}

• class Solution:
def nextClosestTime(self, time: str) -> str:
def check(t):
h, m = int(t[:2]), int(t[2:])
return 0 <= h < 24 and 0 <= m < 60

def dfs(curr):
if len(curr) == 4:
if not check(curr):
return
nonlocal ans, d
p = int(curr[:2]) * 60 + int(curr[2:])
if t < p < t + d:
d = p - t
ans = curr[:2] + ':' + curr[2:]
return
for c in s:
dfs(curr + c)

s = {c for c in time if c != ':'}
t = int(time[:2]) * 60 + int(time[3:])
d = inf
ans = None
dfs('')
if ans is None:
mi = min(int(c) for c in s)
ans = f'{mi}{mi}:{mi}{mi}'
return ans