1736. Latest Time by Replacing Hidden Digits

Problem Description

The given problem presents a scenario where we have a string representation of a time in the format hh:mm. Some of the digits in this string are unknown and are represented by the character ?. Our task is to determine the latest possible valid time that can be formed by replacing these unknown characters with digits.

The constraints are that the time must be valid and fall within the 24-hour clock range from 00:00 to 23:59. This means that hh should be between 00 and 23 and mm should be between 00 and 59.

The problem requires us to find the maximum possible hour and minute combination that can be achieved by substituting the ? with appropriate digits.

Intuition

The intuition behind the solution is to replace each ? with the largest possible digit that will still result in a valid time. Since we want the latest valid time, we prioritize the leftmost unknown digits first, as they have a larger impact on the time value.

For the hours (hh):

• If the first digit is unknown (?), the largest value it can take depends on the second digit. If the second digit is 4 or greater, the first digit can only be 1 otherwise it could lead to an invalid time (e.g., ?4 can't be 24, but 14 is valid). If the second digit is less than 4 or unknown, the first digit can be 2, as we can achieve times up to 23:xx.
• If the second digit of the hours is unknown, its value depends on the first digit. If the first digit is 2, then the second digit can be at most 3 (making 23:xx the latest valid hour). If the first digit is not 2, the second digit can be 9 (making it 19:xx, 09:xx, etc.).

For the minutes (mm):

• If the third digit (minute's tens place) is unknown, it can always be a 5 as the maximum valid value for minutes’ tens place is 59.
• If the fourth digit (minute's ones place) is unknown, it can always be 9 since it's the largest valid digit for the ones place of minutes.

By following this logic, we systematically replace unknown digits with the maximum possible values that retain the time's validity. This approach ensures that the resulting time is the latest possible valid time.

Learn more about Greedy patterns.

Solution Approach

The solution to the problem uses a straightforward, greedy algorithm that iteratively checks each character of the input string. Since strings in Python are immutable, we first convert the time string into a list of characters, which allows us to modify individual characters directly.

The algorithm checks each position where a '?' may appear and replaces it with the highest possible digit that would still form a valid time. Here is a step-by-step breakdown of the implementation:

• Hours (First position, hh:??:??): If the first character is a '?', then we use a conditional statement to determine its value. If the second character is between '4' and '9', then the first character must be '1' since '2' followed by '4' or higher would not be a valid hour. Otherwise, if the second character is '0' to '3' or '?', the first character can be '2' to maintain the largest possible valid hour such as '20', '21', '22', or '23'.

• Hours (Second position, h?:??:??): For the second character, if it is a '?', we check the value of the first character. If the first digit is '2', the second character can at most be '3' to not exceed '23'. If the first character is '0', '1', or '?', the second character can be replaced by '9', producing the latest possible time within the valid range, like '09', '19', or '29' (where '29' would be corrected to '19' since the first digit would have been already set to '1' in the first step).

• Minutes (Third position, hh:??:??): If the third character (ten minute's place) is a '?', we can always set it to '5', since it's the largest digit that can be placed in the tens place of the minutes part of a time, giving us the latest valid minutes such as '50', '51', ... '59'.

• Minutes (Fourth position, hh:mm:?): Similarly, if the last character (one minute's place) is a '?', we replace it with '9', which is the largest possible digit for the one minute's place, while ensuring that the time remains valid.

After these conditional replacements, we join the list of characters back into a string and return the result, which represents the latest valid time that can be obtained by filling in the unknown digits.

Here is the code chunk that executes the described approach:

1class Solution:
2    def maximumTime(self, time: str) -> str:
3        t = list(time)  # Convert the string to a list for mutability.
4        if t[0] == '?':
5            t[0] = '1' if '4' <= t[1] <= '9' else '2'
6        if t[1] == '?':
7            t[1] = '3' if t[0] == '2' else '9'
8        if t[3] == '?':
9            t[3] = '5'
10        if t[4] == '?':
11            t[4] = '9'
12        return ''.join(t)  # Join the list back into a string.

This approach assumes that the given string always has the format hh:mm and contains no more than two '?' characters for the hours and two '?' characters for the minutes. The conditional logic ensures that only valid times are considered, respecting the 24-hour format restrictions.

Example Walkthrough

Given the string 1?:2?, we'll walk through how the solution approach can be applied to find the latest valid time.

1. Starting with the first character (the tens place of the hour), we see that it is already determined and is the digit 1. Since it is not a ?, we leave it as is.

2. The second character (the ones place of the hour) is a ?. Since the first character is 1, which is less than 2, we can replace the ? with the largest possible digit for the ones place of a valid hour, which is 9. Now the string looks like 19:??:??.

3. Next, we look at the third character, which is the tens place of the minutes 2. Since this digit is already defined, there's no ? to replace, we leave it as it is.

4. The fourth character is ?, which represents the ones place of the minutes. Since there are no restrictions other than it being a valid digit (0-9), we replace it with the largest possible digit, 9. Now we have 19:29.

By following the solution approach, the final string 19:29 is the latest valid time that can be obtained by filling in the unknown digits from the original input 1?:2?.

Solution Implementation

Time and Space Complexity

The time complexity of the provided code is O(1) since the input time is always a string of a fixed length, representing the time in the format HH:MM. The operations performed include indexing, comparisons, and value assignments, all of which are done in constant time.

The space complexity of the code is also O(1). The input is converted to a list t, but since the length of the input is fixed to 5 characters (including the separator ':' character), this also takes up a constant amount of additional space. Thus, the amount of memory used does not scale with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.