Next Closest Time

medium string enumeration

Problem

Given a time like '19:34', return the earliest later time you can form by reusing its digits.

Inputtime = '19:34'

Output'19:39'

Digits {1,3,4,9}; the next valid time uses them.

input

def next_closest_time(t):
    h, m = map(int, t.split(':'))
    cur = h * 60 + m; digits = set(t.replace(':', ''))
    for k in range(1, 1441):
        nxt = (cur + k) % 1440
        s = f'{nxt // 60:02d}:{nxt % 60:02d}'
        if set(s.replace(':', '')) <= digits: return s

function nextClosestTime(t) {
  const [h, m] = t.split(':').map(Number);
  const cur = h * 60 + m; const digits = new Set(t.replace(':', ''));
  for (let k = 1; k <= 1440; k++) {
    const nxt = (cur + k) % 1440;
    const s = String(Math.floor(nxt / 60)).padStart(2, '0') + ':' + String(nxt % 60).padStart(2, '0');
    if ([...s.replace(':', '')].every(d => digits.has(d))) return s;
  }
  return t;
}

String nextClosestTime(String t) {
    int cur = Integer.parseInt(t.substring(0, 2)) * 60 + Integer.parseInt(t.substring(3));
    Set ds = new HashSet<>();
    for (char c : t.toCharArray()) if (c != ':') ds.add(c);
    for (int k = 1; k <= 1440; k++) {
        int nx = (cur + k) % 1440;
        String s = String.format("%02d:%02d", nx / 60, nx % 60);
        boolean ok = true; for (char c : s.toCharArray()) if (c != ':' && !ds.contains(c)) { ok = false; break; }
        if (ok) return s;
    }
    return t;
}

string nextClosestTime(string t) {
    int cur = stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3));
    set ds; for (char c : t) if (c != ':') ds.insert(c);
    for (int k = 1; k <= 1440; k++) {
        int nx = (cur + k) % 1440;
        char buf[6]; snprintf(buf, 6, "%02d:%02d", nx / 60, nx % 60);
        string s = buf;
        bool ok = true; for (char c : s) if (c != ':' && !ds.count(c)) { ok = false; break; }
        if (ok) return s;
    }
    return t;
}

Explanation

Instead of cleverly combining digits, we just try every minute forward until we find one that can be built from the original digits. Since a day has only 1440 minutes, brute force is fast and simple.

First we turn the time into a single number of minutes: cur = h * 60 + m. We also collect the set of allowed digits from the input (ignoring the colon).

Then we step ahead one minute at a time. For each step k, we wrap around midnight with (cur + k) % 1440, format it back into HH:MM, and check whether every digit it uses is in our allowed set.

The first time that check passes, we return it — and because we walk forward in order, it is automatically the earliest valid time. The wrap-around means if nothing later in the day works, we loop back to the start of the next day.

Example: "19:34" has digits {1,3,4,9}. Minutes 19:35 through 19:38 need digits not in that set, but 19:39 uses only allowed digits, so the answer is "19:39".

Time: O(1440) Space: O(1)