Problem Description

You are given a string s that represents a time in 12-hour format, where some digits might be replaced with question marks ("?").

The 12-hour time format follows the pattern "HH:MM" where:

• HH represents hours and must be between 00 and 11 (inclusive)
• MM represents minutes and must be between 00 and 59 (inclusive)
• The earliest possible time is 00:00 and the latest is 11:59

Your task is to replace all the "?" characters in the string with valid digits to create a valid 12-hour time. Among all possible valid times you can create, you need to return the latest (maximum) possible time.

For example:

• If s = "1?:?9", you could create times like "10:09", "11:19", "11:29", etc. The latest valid time would be "11:59".
• If s = "0?:5?", valid times include "00:50", "01:51", "09:59", etc. The latest would be "09:59".

The solution works by trying all possible times from the latest (11:59) to the earliest (00:00), checking if each time matches the pattern given in s (where "?" can match any digit). The first matching time found will be the latest possible time.

Intuition

Since we want to find the latest possible valid time, a natural approach is to start checking from the maximum possible time and work our way backwards. This greedy strategy ensures that the first valid time we find will automatically be the latest one.

Think of it like this: if we need to fill in the blanks to make the biggest number possible, we'd try to put the largest digits first. Here, instead of constructing the time digit by digit, we can leverage the fact that there are only a limited number of possible times in 12-hour format - just 12 × 60 = 720 total possibilities.

The key insight is that checking whether a time matches our pattern with "?" wildcards is straightforward - we just need to verify that each non-"?" character in the original string matches the corresponding digit in our candidate time. If they all match, then we can replace the "?" characters with the corresponding digits from that time.

By iterating from 11:59 down to 00:00, we guarantee that:

1. We explore all possible valid times
2. The first match we find is the maximum possible time
3. We don't need complex logic to determine which digit to place where

This brute-force approach is efficient enough because the search space is small (only 720 possibilities), and the matching check for each candidate is O(1) since the string length is fixed at 5 characters.

Solution Approach

The implementation uses a simple enumeration strategy with nested loops to check all possible times from latest to earliest.

Step-by-step breakdown:

1. Outer loop for hours: Iterate through hours from 11 down to 0 using range(11, -1, -1). This ensures we check the latest hours first.

2. Inner loop for minutes: For each hour, iterate through minutes from 59 down to 0 using range(59, -1, -1). This ensures we check the latest minutes first for each hour.

3. Format the time: For each combination of hour h and minute m, create a formatted string t using f"{h:02d}:{m:02d}". The :02d ensures that single-digit numbers are padded with a leading zero (e.g., 9 becomes "09").

4. Pattern matching: Check if the formatted time t matches the pattern in s:

   • Use zip(s, t) to pair up corresponding characters from both strings
   • For each pair (a, b), verify that either a == "?" (wildcard) or a == b (exact match)
   • The expression all(a == b for a, b in zip(s, t) if a != "?") returns True only if all non-wildcard positions match

5. Return first match: As soon as we find a time that matches the pattern, return it immediately. Since we're checking from latest to earliest, this guaranteed to be the maximum valid time.

Example walkthrough with s = "1?:?9":

• Start checking from 11:59: Compare with "1?:?9" → "1" == "1" ✓, "1" matches "?" ✓, "5" matches "?" ✓, "9" == "9" ✓ → Match found!
• Return "11:59"

The algorithm has a time complexity of O(1) since we check at most 720 fixed combinations, and space complexity of O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with s = "0?:5?":

Step 1: Start from the latest possible time (11:59) and work backwards

We'll check each time to see if it matches our pattern "0?:5?".

Step 2: Check 11:59

• Compare "11:59" with "0?:5?"
• Position 0: "1" vs "0" → No match (we need "0", not "1")
• Skip this time

Step 3: Check 11:58

• Compare "11:58" with "0?:5?"
• Position 0: "1" vs "0" → No match
• Skip this time

Step 4: Continue checking... (skipping hours 11 and 10)

All times starting with "11:" or "10:" will fail because they don't start with "0".

Step 5: Check 09:59

• Compare "09:59" with "0?:5?"
• Position 0: "0" vs "0" → Match! ✓
• Position 1: "9" vs "?" → Match! (wildcard) ✓
• Position 2: ":" vs ":" → Match! ✓
• Position 3: "5" vs "5" → Match! ✓
• Position 4: "9" vs "?" → Match! (wildcard) ✓

Step 6: Return the result

Since all positions match, "09:59" is valid. Because we're checking from latest to earliest, this is the maximum possible time.

The algorithm replaces:

• The first "?" (position 1) with "9"
• The second "?" (position 4) with "9"

Final answer: "09:59"

Solution Implementation

Time and Space Complexity

The time complexity is O(h × m), where h = 12 and m = 60. The algorithm iterates through all possible hours from 11 down to 0 (12 iterations) and for each hour, iterates through all possible minutes from 59 down to 0 (60 iterations). In the worst case, when the match is found at "00:00" or no match exists, the algorithm checks all 12 × 60 = 720 possible time combinations. For each combination, the zip and all operations take O(5) time (constant, as the time string has fixed length of 5 characters), which doesn't affect the overall complexity.

The space complexity is O(1). The algorithm only uses a constant amount of extra space regardless of input size. The variables h, m, and t occupy fixed space, and the string t is always 5 characters long. The zip operation creates an iterator that doesn't store all pairs in memory at once, maintaining constant space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Hour Range Assumption

A common mistake is assuming the 12-hour format uses hours from 01 to 12 instead of 00 to 11. This misunderstanding comes from confusing the display format with the actual valid range in the problem.

Incorrect approach:

for hour in range(12, 0, -1):  # Wrong: tries 12:xx which is invalid
    for minute in range(59, -1, -1):
        current_time = f"{hour:02d}:{minute:02d}"
        # This would generate invalid times like "12:00"

Correct approach:

for hour in range(11, -1, -1):  # Correct: uses 00-11 range
    for minute in range(59, -1, -1):
        current_time = f"{hour:02d}:{minute:02d}"

2. String Formatting Without Zero Padding

Forgetting to pad single-digit numbers with leading zeros will cause pattern matching failures.

Incorrect approach:

current_time = f"{hour}:{minute}"  # Wrong: produces "1:5" instead of "01:05"

Correct approach:

current_time = f"{hour:02d}:{minute:02d}"  # Correct: ensures "01:05" format

3. Wrong Iteration Direction

Starting from the earliest time (00:00) and returning the last match instead of starting from the latest time (11:59) and returning the first match. This makes the code unnecessarily complex and requires storing all matches.

Incorrect approach:

valid_times = []
for hour in range(12):  # Wrong: starts from earliest
    for minute in range(60):
        current_time = f"{hour:02d}:{minute:02d}"
        if is_match(s, current_time):
            valid_times.append(current_time)
return valid_times[-1] if valid_times else ""  # Needs extra storage

Correct approach:

for hour in range(11, -1, -1):  # Correct: starts from latest
    for minute in range(59, -1, -1):
        current_time = f"{hour:02d}:{minute:02d}"
        if is_match(s, current_time):
            return current_time  # Return immediately

4. Overly Complex Pattern Matching

Using regular expressions or complex string manipulation when simple character-by-character comparison suffices.

Overcomplicated approach:

import re
pattern = s.replace("?", "\\d")
if re.match(pattern, current_time):
    # Unnecessary regex overhead

Simple and correct approach:

is_valid_match = all(
    pattern_char == time_char 
    for pattern_char, time_char in zip(s, current_time) 
    if pattern_char != "?"
)