Latest Time You Can Obtain After Replacing Characters

Difficulty: Easy | Acceptance: 35.30% | Paid: No Topics: String, Enumeration

You are given a string s in the format “HH:MM” representing a time. Some digits in s are hidden (represented by ’?’). Return the latest valid time you can obtain by replacing the hidden characters.

• Examples
• Constraints
• Greedy Replacement
• Brute Force Enumeration

Examples

Example 1

Input:

s = "1?:?4"

Output:

"11:54"

Explanation: The latest 12-hour format time we can achieve by replacing ”?” characters is “11:54”.

Example 2

Input:

s = "0?:5?"

Output:

"09:59"

Explanation: The latest 12-hour format time we can achieve by replacing ”?” characters is “09:59”.

Constraints

- s.length == 5
- s[2] is equal to the character ":".
- All characters except s[2] are digits or "?" characters.
- The input is generated such that there is at least one time between "00:00" and "11:59" that you can obtain after replacing the "?" characters.

Greedy Replacement

Intuition We can determine the maximum digit for each position independently based on the constraints of the time format and the fixed digits already present.

Steps

• Convert the string to a mutable list or array of characters.
• If the first digit is ’?’, check the second digit. If the second digit is ’?’ or less than or equal to ‘3’, the first digit can be ‘2’. Otherwise, it must be ‘1’.
• If the second digit is ’?’, check the first digit. If the first digit is ‘2’, the second digit can be at most ‘3’. Otherwise, it can be ‘9’.
• If the third digit (first minute digit) is ’?’, set it to ‘5’ (maximum for tens place of minutes).
• If the fourth digit (second minute digit) is ’?’, set it to ‘9’ (maximum for ones place of minutes).
• Join the characters back into a string and return.

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

Complexity

• Time: O(1)
• Space: O(1)
• Notes: We perform a constant number of operations regardless of input size.

Brute Force Enumeration

Intuition Since the total number of valid times in a day is small (24 * 60 = 1440), we can iterate backwards from the latest possible time (“23:59”) to the earliest (“00:00”) and return the first time that matches the pattern.

Steps

• Iterate hours from 23 down to 0.
• Iterate minutes from 59 down to 0.
• Format the current time as a string “HH:MM”.
• Compare this string with the input s. If a character in s is not ’?’ and does not match the corresponding character in the generated time, the time is invalid.
• Return the first valid time found.

class Solution:
    def maximumTime(self, s: str) -> str:
        for h in range(23, -1, -1):
            for m in range(59, -1, -1):
                time = "%02d:%02d" % (h, m)
                valid = True
                for i in range(5):
                    if s[i] != '?' and s[i] != time[i]:
                        valid = False
                        break
                if valid:
                    return time
        return ""

Complexity

• Time: O(1) - Specifically O(24 * 60 * 5), which is constant.
• Space: O(1)
• Notes: Less efficient than the greedy approach but conceptually simple and robust.