Problem Description

The "Latest Time by Replacing Hidden Digits" problem gives you a string time representing a time in the format "hh:mm". Some digits in the string are replaced with the character '?'. Your task is to replace every '?' with a digit (0-9) to make the latest valid 24-hour time possible.

• Each '?' must be replaced with a single digit.
• The final string must be a valid time in 24-hour format (00:00 to 23:59).
• There is always at least one valid solution.
• Do not reuse or swap digits; only replace '?' in place.

For example, given time = "?4:5?", your goal is to replace both '?' so the resulting time is as late as possible and still valid.

Thought Process

The problem requires maximizing the time, so we want to choose the largest possible digit for each '?'. However, constraints for valid hours (00 to 23) and minutes (00 to 59) limit which digits are allowed in each position.

• For the hour part (hh), the first digit can be at most 2, but if it's 2, the second digit can only be 0-3.
• For the minute part (mm), the first digit can be at most 5.
• We check each character: if it's '?', we pick the largest digit possible that keeps the time valid.

A brute-force approach would try all possible digit combinations, but that's unnecessary. Instead, by analyzing each position independently, we can decide the best digit for each '?' based on the adjacent digits.

Solution Approach

Let's break down the algorithm step-by-step:

1. Examine Each Character: Iterate over each character in the time string.
2. Handle Hours:
   • If the first hour digit (time[0]) is '?':
     • If the second hour digit is unknown or less than '4', use '2' (so the hour can be as late as 23).
     • If the second hour digit is '4' or greater, use '1' (since '24' is invalid).
   • If the second hour digit (time[1]) is '?':
     • If the first hour digit is '2', use '3' (so the hour can be 23).
     • Otherwise, use '9' (so the hour can be 19, 09, etc.).
3. Handle Minutes:
   • If the first minute digit (time[3]) is '?', use '5' (so the minute can be 59).
   • If the second minute digit (time[4]) is '?', use '9'.
4. Return the Modified String: After replacing all '?' with the appropriate digits, return the new string.

This approach is efficient because it only requires a single pass and simple logic at each character.

Example Walkthrough

Let's use the input time = "?4:5?" as an example:

1. First character: '?' (hour tens place).
   • The second character is '4', which is greater than '3', so the highest valid first digit is '1'.
   • So, replace '?' with '1'.
2. Second character: '4' (hour ones place), already known.
3. Third character: ':' (separator), skip.
4. Fourth character: '5' (minute tens place), already known.
5. Fifth character: '?' (minute ones place).
   • Replace with '9' to make the minute as late as possible.

The result is "14:59", which is the latest valid time possible by replacing the hidden digits.

Time and Space Complexity

• Brute-force Approach: Would try all possible combinations for each '?' (potentially up to 10ⁿ for n question marks), but this is unnecessary and inefficient.
• Optimized Approach:
  • Time Complexity: O(1), because the input is always 5 characters and we check each character once.
  • Space Complexity: O(1), as we only store a few variables and the result string.

Summary

The key to solving "Latest Time by Replacing Hidden Digits" is understanding the constraints of each digit in the 24-hour time format. By making greedy choices—always selecting the largest valid digit for each '?'—we efficiently construct the latest possible valid time. This method is both simple and optimal, requiring only a single scan through the string and constant space.

Code Implementation

class Solution:
    def maximumTime(self, time: str) -> str:
        res = list(time)
        # Hour tens
        if res[0] == '?':
            if res[1] == '?' or res[1] <= '3':
                res[0] = '2'
            else:
                res[0] = '1'
        # Hour ones
        if res[1] == '?':
            if res[0] == '2':
                res[1] = '3'
            else:
                res[1] = '9'
        # Minute tens
        if res[3] == '?':
            res[3] = '5'
        # Minute ones
        if res[4] == '?':
            res[4] = '9'
        return ''.join(res)
      

class Solution {
public:
    string maximumTime(string time) {
        string res = time;
        // Hour tens
        if (res[0] == '?') {
            if (res[1] == '?' || res[1] <= '3') res[0] = '2';
            else res[0] = '1';
        }
        // Hour ones
        if (res[1] == '?') {
            if (res[0] == '2') res[1] = '3';
            else res[1] = '9';
        }
        // Minute tens
        if (res[3] == '?') res[3] = '5';
        // Minute ones
        if (res[4] == '?') res[4] = '9';
        return res;
    }
};
      

class Solution {
    public String maximumTime(String time) {
        char[] res = time.toCharArray();
        // Hour tens
        if (res[0] == '?') {
            if (res[1] == '?' || res[1] <= '3') res[0] = '2';
            else res[0] = '1';
        }
        // Hour ones
        if (res[1] == '?') {
            if (res[0] == '2') res[1] = '3';
            else res[1] = '9';
        }
        // Minute tens
        if (res[3] == '?') res[3] = '5';
        // Minute ones
        if (res[4] == '?') res[4] = '9';
        return new String(res);
    }
}
      

var maximumTime = function(time) {
    let res = time.split('');
    // Hour tens
    if (res[0] === '?') {
        if (res[1] === '?' || res[1] <= '3') res[0] = '2';
        else res[0] = '1';
    }
    // Hour ones
    if (res[1] === '?') {
        if (res[0] === '2') res[1] = '3';
        else res[1] = '9';
    }
    // Minute tens
    if (res[3] === '?') res[3] = '5';
    // Minute ones
    if (res[4] === '?') res[4] = '9';
    return res.join('');
};