Latest Time by Replacing Hidden Digits

Latest Time by Replacing Hidden Digits

1. What is this problem about?

The Latest Time by Replacing Hidden Digits coding problem gives you a string representing a 12-hour or 24-hour time (usually 24-hour) with some digits replaced by '?'. You need to replace all '?' characters with digits such that the resulting time is valid and is the latest possible time.

2. Why is this asked in interviews?

Google asks this "Easy" level question to test basic conditional logic and greedy decision-making. Since the constraints are very small (only 4 digits to consider), the problem focuses on the candidate's ability to handle all the "if-else" cases correctly, specifically the dependencies between digits (e.g., the second digit of the hour depends on whether the first digit is '0', '1', or '2').

3. Algorithmic pattern used

This problem follows the String and Greedy interview pattern. Because we want the latest time, we greedily pick the largest valid digit for each position from left to right.

• For the first hour digit (HH): Pick '2' if the second digit is '?' or <= 3; else pick '1'.
• For the second hour digit: If the first is '2', pick '3'; else pick '9'.
• For the first minute digit (MM): Always pick '5'.
• For the second minute digit: Always pick '9'.

4. Example explanation

Time: "1?:??"

1. First digit '1' is fixed.
2. Second hour digit '?': Since first is '1', the latest valid is '9'. Time: "19:??"
3. First minute digit '?': Latest valid is '5'. Time: "19:5?"
4. Second minute digit '?': Latest valid is '9'. Time: "19:59" Result: "19:59".

If it was "?4:??":

1. First hour digit '?': Second is '4' (> 3), so we can't use '2'. Pick '1'.
2. Second digit '4' is fixed.
3. Minute digits become '5' and '9'. Result: "14:59".

5. Common mistakes candidates make

The biggest mistake is the hour logic. Specifically, candidates often forget that if the second digit is '?', they can make the hour "23". If they greedily set the first digit to '2' without checking the second, they might run into issues if the second was already fixed at something like '7' (making it "27", which is invalid).

6. Interview preparation tip

For "String, Greedy interview pattern" problems, handle each position one by one but be mindful of "look-ahead" dependencies. In time problems, the first two digits are a pair and should be handled with a clear understanding of the 00-23 range.