We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Latest Time by Replacing Hidden Digits

Number: 1858

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given a time string in the format "hh:mm" where some digits might be hidden and represented by '?', determine the latest valid time (in "hh:mm" format) possible by replacing each '?' with a digit such that the time is between "00:00" and "23:59".

Key Insights

  • Treat each digit position individually with specific constraints.
  • For the hour:
    • For the tens place (first digit): if unknown, choose '2' if it does not force an invalid hour; otherwise, choose '1'.
    • For the ones place (second digit): if unknown and the tens digit is '2', only '0' to '3' are allowed; otherwise, up to '9'.
  • For the minutes:
    • The tens digit must be at most '5'.
    • The ones digit can be any digit from '0' to '9'.
  • A simple greedy strategy works by replacing each '?' with the maximum valid digit for that position.

Space and Time Complexity

Time Complexity: O(1) – The solution processes a constant number of characters. Space Complexity: O(n) – The space required to build the new string (where n is the number of characters in the input, which is constant 5 in this case).

Solution

We iterate over the positions in the input time string "hh:mm" and replace any '?' with the highest digit possible without violating the time format constraints.

Step-by-step:

  1. For the hour tens (first character):
    • If it's '?', check the hour ones digit. If the ones digit is not '?' and is greater than '3' (since hours starting with '2' allow only 0-3 in the ones place), choose '1'; otherwise, choose '2'.
  2. For hour ones (second character):
    • If it's '?', if the tens digit is '2', choose '3' (the maximum allowed value when the first digit is '2'). Otherwise, choose '9'.
  3. For minute tens (fourth character):
    • If it's '?', replace it with '5' (minutes tens digit can only be 0-5).
  4. For minute ones (fifth character):
    • If it's '?', replace it with '9' as minutes' ones digit can go from 0-9.

This greedy replacement ensures the constructed time is the latest valid time possible.

Code Solutions

# Python solution with line-by-line comments
def maximumTime(time: str) -> str:
    # Convert the time string to a list of characters for easy modification.
    time_chars = list(time)
    
    # Process the first digit of the hour
    if time_chars[0] == '?':
        # If the second digit is known and > '3', we cannot use '2' because 24+ is invalid.
        if time_chars[1] != '?' and int(time_chars[1]) > 3:
            time_chars[0] = '1'
        else:
            time_chars[0] = '2'

    # Process the second digit of the hour
    if time_chars[1] == '?':
        # If the first digit is '2', the maximum valid second digit is '3'
        if time_chars[0] == '2':
            time_chars[1] = '3'
        else:
            time_chars[1] = '9'

    # Process the minute tens digit
    if time_chars[3] == '?':
        time_chars[3] = '5'
    
    # Process the minute ones digit
    if time_chars[4] == '?':
        time_chars[4] = '9'
    
    # Convert the list of characters back to a string and return.
    return "".join(time_chars)

# Example usage:
# print(maximumTime("2?:?0"))  # Outputs: "23:50"
← Back to All Questions