Naive Approach

A brute-force approach would involve iterating through all possible times (00:00 to 23:59) and checking if each time matches the given pattern, where '?' can be any digit. The largest time that satisfies the condition would be the answer.

Code (Python)

def solve():
    time = input()
    ans = ""
    for h in range(24):
        for m in range(60):
            hh = str(h).zfill(2)
            mm = str(m).zfill(2)
            curr = hh + ":" + mm
            ok = True
            for i in range(5):
                if time[i] == '?':
                    continue
                if time[i] != curr[i]:
                    ok = False
                    break
            if ok:
                if ans == "" or curr > ans:
                    ans = curr
    print(ans)

Big O Analysis

• Time Complexity: O(24 * 60 * 5) = O(1), because we iterate through all possible times which is constant.
• Space Complexity: O(1)

Optimal Approach

The optimal approach is to fill in the question marks from left to right, maximizing each digit while ensuring the resulting time is valid.

1. First digit of hour (time[0]):
   • If it's '?', and the second digit is also '?', then set it to '2'.
   • If it's '?', and the second digit is less than '4', then set it to '2'.
   • Otherwise, set it to '1'.
2. Second digit of hour (time[1]):
   • If it's '?', and the first digit is '2', then set it to '3'.
   • If it's '?', set it to '9'.
3. First digit of minute (time[3]):
   • If it's '?', set it to '5'.
4. Second digit of minute (time[4]):
   • If it's '?', set it to '9'.

Code (Python)

def maximum_time(time: str) -> str:
    time_list = list(time)

    if time_list[0] == '?':
        if time_list[1] == '?' or int(time_list[1]) <= 3:
            time_list[0] = '2'
        else:
            time_list[0] = '1'

    if time_list[1] == '?':
        if time_list[0] == '2':
            time_list[1] = '3'
        else:
            time_list[1] = '9'

    if time_list[3] == '?':
        time_list[3] = '5'

    if time_list[4] == '?':
        time_list[4] = '9'

    return "".join(time_list)

Big O Analysis

• Time Complexity: O(1), since we only iterate through the string once, and the string has a fixed length.
• Space Complexity: O(1), since we only use a constant amount of extra space.

Edge Cases

• The input string time is guaranteed to be in the format "hh".
• The input string time is guaranteed to produce a valid time.