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.

Thinking Process

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.

  • Strings often need frequency maps or two-pointer scans.
  • Watch index bounds and empty-string edge cases.
  • Stack helps with nested or repeated patterns.
Two pointers 1 3 5 7 9 L R move L/R based on comparison

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Two pointers on string (this problem) O(n) O(1) Palindrome, parsing
Hash map / frequency O(n) O(k) Anagram, character counts
KMP / rolling hash O(n) O(n) Pattern matching
Stack parsing O(n) O(n) Decode string, parentheses

Examples

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 is in the format "HH:MM".
  • 0 <= HH < 24
  • 0 <= MM < 60

Algorithm Breakdown

Key Insight: Time Wrapping

The algorithm handles day wrapping correctly:

class Solution:
    def nextClosestTime(self, time: str) -> str:
        # extract digits
        allowed = set(time[:2] + time[3:])

        h = int(time[:2])
        m = int(time[3:])
        start = h * 60 + m

        def valid(x):
            return all(d in allowed for d in f"{x//60:02d}{x%60:02d}")

        for i in range(1, 24 * 60 + 1):
            nxt = (start + i) % (24 * 60)
            if valid(nxt):
                return f"{nxt//60:02d}:{nxt%60:02d}"

This ensures that after 23:59, we continue checking from 00:00 of the next day.

Digit Validation

For each candidate time, we check all four digit positions:

  • Hour tens: h1 / 10 (0-2)
  • Hour ones: h1 % 10 (0-9)
  • Minute tens: m1 / 10 (0-5)
  • Minute ones: m1 % 10 (0-9)

All four digits must be in the allowed set.

Time Range

The loop checks from start + 1 to end:

  • start + 1: Next minute after current time
  • end = getMin(h + 24, m): Current time + 24 hours
  • This covers the entire next 24-hour period

Complexity

Time Complexity: O(1)

  • Maximum iterations: At most 1440 minutes (24 hours)
  • Each iteration: O(1) - constant time digit checks
  • Total: O(1) - bounded by constant 1440

Space Complexity: O(1)

  • Allowed digits array: O(10) = O(1)
  • Variables: O(1)
  • Total: O(1)

Key Points

  1. Digit Reuse: Any digit can be used multiple times
  2. Next Day: Solution may wrap to next day if no valid time in current day
  3. Time Format: Always output in "HH:MM" format with leading zeros
  4. Brute Force: Check all possible times until valid one found
  5. Efficient: O(1) time complexity since bounded by 24 hours

Detailed Example Walkthrough

Example: time = "12:09"

Step 1: Parse input
h = 12, m = 9
start = getMin(12, 9) = 12*60 + 9 = 729 minutes

Step 2: Build allowed digits
con = [true, true, true, false, false, false, false, false, false, true]
      (digits 0, 1, 2, 9 are allowed)

Step 3: Simulate time progression
i = 730 (12:10): h1=12, m1=10
  - h1/10 = 1 ✓, h1%10 = 2 ✓, m1/10 = 1 ✓, m1%10 = 0 ✓
  - Valid! Result: "12:10"

Example: time = "01:00"

Step 1: Parse input
h = 1, m = 0
start = getMin(1, 0) = 60 minutes

Step 2: Build allowed digits
con = [true, true, false, false, false, false, false, false, false, false]
      (digits 0, 1 are allowed)

Step 3: Simulate time progression
i = 61 (01:01): h1=1, m1=1
  - h1/10 = 0 ✓, h1%10 = 1 ✓, m1/10 = 0 ✓, m1%10 = 1 ✓
  - Valid! Result: "01:01"

Edge Cases

  1. Same digits: "11:11" → next valid time using only 1s
  2. All zeros: "00:00" → next time using only 0s (00:00 again if wrapping)
  3. Late in day: "23:59" → may wrap to next day
  4. Single digit set: "00:00" or "11:11" → limited options

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Tags

String, Simulation, Brute Force, Time, Medium

Key Takeaways

  • Strings often need frequency maps or two-pointer scans.
  • Watch index bounds and empty-string edge cases.
  • Stack helps with nested or repeated patterns.

References

Template Reference