Latest Time You Can Obtain After Replacing Characters - Solution & Explanation

Problem Overview: You receive a time string in the format hh:mm where some characters are replaced with '?'. Each '?' can be replaced with a digit. The goal is to produce the latest valid time possible while respecting the constraints of the clock format.

The hours must form a valid value between 00 and 11, and minutes must be between 00 and 59. Because every unknown digit can be chosen freely, the strategy is to maximize the time while keeping the result valid.

Approach 1: Brute Force Simulation (Time: O(1), Space: O(1))

Enumerate every valid time from 11:59 down to 00:00 and check whether it matches the pattern of the input string. A time matches if each digit either equals the corresponding character or the input contains '?' at that position. Once a match is found, return it immediately because the search starts from the latest time.

This works because the total number of possibilities is very small (12 × 60 = 720). Even a full scan is constant time. The approach demonstrates the problem constraints clearly and relies on simple enumeration and string comparison.

Approach 2: Greedy Replacement (Time: O(1), Space: O(1))

The optimal solution replaces each '?' with the largest digit that still keeps the time valid. Start with the hour digits. If the first hour digit is '?', choose '1' when the second digit is '?' or ≤ '1'; otherwise choose '0'. This guarantees the hour does not exceed 11. If the second hour digit is '?', pick '1' when the first digit is '1', otherwise use '9' to maximize values like 09.

For the minutes, the constraints are simpler. Replace the first minute digit with '5' if it is '?', and the last digit with '9'. These are the largest values that keep minutes within 00–59.

The greedy method works because each position has a locally optimal choice that never blocks a larger valid time later. The logic operates directly on the string and performs a few conditional checks. This makes it both faster to implement and easier to reason about than scanning every candidate. The solution mainly involves manipulating a string and applying simple greedy decisions.

Recommended for interviews: The greedy replacement approach is what interviewers typically expect. It shows you understand the constraints of the time format and can derive the maximum valid digit for each position. Mentioning the brute force enumeration first demonstrates problem exploration, but implementing the greedy logic highlights stronger algorithmic thinking.