1736. Latest Time by Replacing Hidden Digits

Problem Description

Given a string time representing time in "hh:mm" format, where some digits are hidden ('?'), find the latest valid time by replacing the hidden digits. Valid times are between 00:00 and 23:59.

Solution: Greedy Approach

The most efficient way to solve this problem is using a greedy approach. We iterate through the time string and fill in the '?' characters one by one, always choosing the largest possible digit while ensuring the resulting time is valid.

Here's a breakdown of the approach:

1. Hours:

   • If the first digit (time[0]) is '?', we check the second digit (time[1]):
     • If time[1] is between '4' and '9', the largest possible first digit is '1'.
     • Otherwise, the largest possible first digit is '2'.
   • If the second digit (time[1]) is '?', we check the first digit (time[0]):
     • If time[0] is '2', the largest possible second digit is '3'.
     • Otherwise, the largest possible second digit is '9'.

2. Minutes:

   • If the third digit (time[3]) is '?', the largest possible digit is '5'.
   • If the fourth digit (time[4]) is '?', the largest possible digit is '9'.

Code Implementation (Python)

class Solution:
    def maximumTime(self, time: str) -> str:
        time_list = list(time)
 
        if time_list[0] == '?':
            time_list[0] = '2' if time_list[1] == '?' or int(time_list[1]) < 4 else '1'
        if time_list[1] == '?':
            time_list[1] = '9' if time_list[0] == '1' or time_list[0] == '?' else '3'  
        if time_list[3] == '?':
            time_list[3] = '5'
        if time_list[4] == '?':
            time_list[4] = '9'
 
        return "".join(time_list)

Code Implementation (Java)

class Solution {
    public String maximumTime(String time) {
        char[] timeArray = time.toCharArray();
 
        if (timeArray[0] == '?') {
            timeArray[0] = (timeArray[1] == '?' || timeArray[1] < '4') ? '2' : '1';
        }
        if (timeArray[1] == '?') {
            timeArray[1] = (timeArray[0] == '2') ? '3' : '9';
        }
        if (timeArray[3] == '?') {
            timeArray[3] = '5';
        }
        if (timeArray[4] == '?') {
            timeArray[4] = '9';
        }
 
        return new String(timeArray);
    }
}

Code Implementation (JavaScript)

/**
 * @param {string} time
 * @return {string}
 */
var maximumTime = function(time) {
    let timeArray = time.split('');
 
    if (timeArray[0] === '?') {
        timeArray[0] = (timeArray[1] === '?' || parseInt(timeArray[1]) < 4) ? '2' : '1';
    }
    if (timeArray[1] === '?') {
        timeArray[1] = (timeArray[0] === '2') ? '3' : '9';
    }
    if (timeArray[3] === '?') {
        timeArray[3] = '5';
    }
    if (timeArray[4] === '?') {
        timeArray[4] = '9';
    }
 
    return timeArray.join('');
};

Time and Space Complexity

• Time Complexity: O(1) - We perform a constant number of operations regardless of the input size (the time string is always of fixed length).
• Space Complexity: O(1) - We use a constant amount of extra space to store the character array. The space used is independent of the input size.

The solution efficiently determines the latest possible valid time by making greedy choices based on the available digits and constraints. The constant time and space complexity makes it highly efficient for this specific problem.