Latest Time by Replacing Hidden Digits: Greedy Position-by-Position

You are given a string time in the format "HH:MM" where some digits have been replaced with the character '?'. Your task is to replace every '?' with a digit so that the resulting time is the latest (maximum) valid time in 24-hour format. Hours range from 00 to 23, and minutes range from 00 to 59.

This is LeetCode 1736: Latest Time by Replacing Hidden Digits, an easy problem that tests your ability to make greedy decisions at each position of a string while respecting constraints between positions.

Why this problem matters

This problem is a clean exercise in greedy decision-making with local constraints. Unlike many greedy problems where you scan a full array, here you have a fixed-size input (exactly 5 characters) and each position has its own rule. The challenge is identifying the right rule for each slot.

What makes it interesting is that positions 0 and 1 are not independent. The valid range for the ones digit of the hour depends on the tens digit, and vice versa. This kind of constraint propagation between adjacent positions shows up in scheduling, parsing, and validation problems.

If you can break down a structured string into individual positions, figure out the constraint for each one, and apply a greedy maximum, you have a reusable skill. The same thinking applies to problems involving dates, IP addresses, version numbers, and other formatted strings.

The key insight

Process each position from left to right, replacing '?' characters one at a time. For each '?', pick the largest digit that keeps the time valid. The rules are:

• Position 0 (H tens): If position 1 is <= 3 or '?', pick 2. Otherwise pick 1. You want the hour to be as large as possible, but 2 only works when H1 is 0, 1, 2, or 3 (since valid hours go up to 23).
• Position 1 (H ones): If position 0 is '2', pick 3 (since 23 is the max hour starting with 2). Otherwise pick 9 (since 19 is valid).
• Position 3 (M tens): Always pick 5. Minutes go up to 59, so the tens digit maxes out at 5.
• Position 4 (M ones): Always pick 9. No constraint from other positions.

Each '?' is replaced only when it is actually '?'. Fixed digits are left alone.

The solution

def maximum_time(time: str) -> str:
    t = list(time)

    if t[0] == '?':
        t[0] = '2' if t[1] in '?0123' else '1'
    if t[1] == '?':
        t[1] = '3' if t[0] == '2' else '9'
    if t[3] == '?':
        t[3] = '5'
    if t[4] == '?':
        t[4] = '9'

    return ''.join(t)

Here is what each check does:

1. Position 0: We check t[1] to decide. If the ones digit of the hour is '?' or in {0, 1, 2, 3}, we can safely use 2 as the tens digit (giving hours 20-23). If H1 is 4 through 9, then 2X would exceed 23, so we fall back to 1.
2. Position 1: We check t[0] (which may have just been resolved). If the tens digit is 2, the max ones digit is 3. Otherwise the tens digit is 0 or 1, and any ones digit up to 9 is valid.
3. Position 3: The tens digit of minutes is independent. The maximum is 5 (for 50-59).
4. Position 4: The ones digit of minutes is fully independent. The maximum is always 9.

Visual walkthrough

Complexity analysis

The input is always exactly 5 characters. We do a fixed number of comparisons and assignments, so both time and space are constant regardless of any external factor. There is no loop over variable-length input.

The building blocks

1. Greedy position-by-position replacement

The core pattern is scanning a fixed-format string and making the locally optimal choice at each position:

if t[position] == '?':
    t[position] = best_valid_digit(position, t)

You check whether the current character needs replacing, then pick the largest digit that satisfies the constraint for that position. This pattern reappears whenever you parse or construct formatted strings like times, dates, or IP addresses.

2. Constraint propagation between dependent positions

Positions 0 and 1 have a mutual constraint: the pair (H0, H1) must form a number between 00 and 23. When one of them is '?', your choice depends on the other:

# Position 0 looks at position 1
if t[0] == '?':
    t[0] = '2' if t[1] in '?0123' else '1'

# Position 1 looks at (now resolved) position 0
if t[1] == '?':
    t[1] = '3' if t[0] == '2' else '9'

Processing order matters. By resolving position 0 first, position 1 can read the final value of position 0. This left-to-right resolution is a simple form of constraint propagation that avoids backtracking.

Edge cases

• "??:??" should return "23:59": Every position is unknown, so you pick the global maximum time.
• "2?:?0" should return "23:50": H0 is 2, so H1 maxes at 3. M0 maxes at 5. M1 is fixed at 0.
• "0?:4?" should return "09:49": H0 is 0, so H1 can go up to 9. M0 is fixed at 4. M1 maxes at 9.
• "?4:5?" should return "14:59": Position 0 cannot be 2 because position 1 is 4 (hour 24 is invalid). So H0 becomes 1. M1 becomes 9.

From understanding to recall

You have read through the solution and the logic feels obvious. Four positions, four rules, one dependency. But in an interview, forgetting that H0 depends on H1 (not the other way around) or mixing up the '2' vs '1' threshold is easy to do under pressure.

Spaced repetition helps you internalize the pattern so that it becomes automatic. You practice writing the four conditionals from memory, and after a few rounds you do not need to re-derive the rules. You see "replace hidden digits in a formatted string" and the position-by-position greedy approach comes out immediately.

The greedy replacement pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the ideas stick.

Related posts

• Valid Palindrome - Character-by-character string processing
• Length of Last Word - Simple string parsing with edge cases
• Add Binary - Position-by-position string construction

CodeBricks breaks the latest time by replacing hidden digits problem into its greedy replacement and constraint propagation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy string construction question shows up in your interview, you do not think about it. You just write it.