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 You Can Obtain After Replacing Characters

Number: 3361

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given a string s that represents a 12‐hour format time "HH:MM" where some of the digits are replaced with "?", replace every "?" with a digit so that the resulting time is valid and is the latest possible time. Valid hours range from "00" to "11" and valid minutes from "00" to "59".

Key Insights

  • The hour tens digit (first character) can only be "0" or "1" because valid hours are between "00" and "11".
  • For the hour ones digit, if the tens digit is "1", then the maximum digit allowed is "1" (making "11") while if the tens digit is "0", the maximum valid formation is "09".
  • The minutes tens digit must be at most "5" (as minutes go from "00" to "59").
  • The minute ones digit can be replaced with "9" to maximize the minutes.

Space and Time Complexity

Time Complexity: O(1) – Each character is examined and replaced if necessary. Space Complexity: O(1) – A fixed amount of extra space is used.

Solution

The approach is straightforward and uses a greedy strategy:

  1. Convert the string into a mutable array (or similar structure) to easily update characters.
  2. For the hour part:
    • If the tens digit is "?", replace it with "1" (the maximum allowed for a valid hour in a 12-hour format).
    • For the ones digit, if it is "?", set it based on the fixed tens digit; if the tens digit is "1", replace with "1" (yielding "11"), otherwise replace with "9" (yielding "09").
  3. For the minutes:
    • If the minutes tens digit is "?", replace it with "5".
    • If the minute ones digit is "?", replace it with "9".
  4. Return the modified string.

This method uses constant extra space and iterates over a fixed length string, leading to O(1) time.

Code Solutions

Below are code implementations in Python, JavaScript, C++, and Java with detailed comments.

def latestTime(s: str) -> str:
    # Convert the input string to a list for easy manipulation.
    s = list(s)
    
    # For hour tens position: valid values are only '0' or '1'. We choose '1' to maximize.
    if s[0] == '?':
        s[0] = '1'
    
    # For hour ones position: if unknown, choose based on the tens digit.
    # If tens digit is '1', maximum valid hour is "11"; otherwise (tens digit is '0'), "09" is maximum.
    if s[1] == '?':
        s[1] = '1' if s[0] == '1' else '9'
    
    # For minute tens position, the maximum valid digit is '5' to ensure minutes are less than 60.
    if s[3] == '?':
        s[3] = '5'
    
    # For minute ones position, choose '9' to maximize the minutes.
    if s[4] == '?':
        s[4] = '9'
    
    # Convert the list back to a string and return.
    return "".join(s)

# Example usage:
print(latestTime("1?:?4"))  # Output: "11:54"
print(latestTime("0?:5?"))  # Output: "09:59"
← Back to All Questions