Domain 1EasyCORE

Latest Time by Replacing Hidden Digits

The problem requires us to replace hidden digits in a given time string `hh:mm` with the largest possible values to form the latest valid time. The input is a string where some characters are replaced by `?`, and we need to determine the maximum valid time that can be formed by replacing these `?`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String#Greedy

1736. Latest Time by Replacing Hidden Digits

Model: qwen2.5-coder:14b
Topics: String,Greedy
FAANG asked: 1
Acceptance rate: 41.3%


Problem Breakdown

The problem requires us to replace hidden digits in a given time string hh:mm with the largest possible values to form the latest valid time. The input is a string where some characters are replaced by ?, and we need to determine the maximum valid time that can be formed by replacing these ?.

Inputs:

  • A string time in the format hh:mm where some digits are hidden (represented by ?).

Outputs:

  • A string representing the latest valid time.

Implicit Constraints or Tricky Edge Cases:

  • The hour part must be between 00 and 23.
  • The minute part must be between 00 and 59.
  • We need to handle cases where multiple digits are hidden.
  • The input is guaranteed to produce a valid time, so we don’t need to check for invalid inputs.

Intuition

A brute-force approach would involve trying all possible combinations of digits (0-9) for each ? and checking if the resulting time is valid. However, this approach is inefficient with a time complexity of O(10^4), which is not optimal given that we can determine the maximum value for each digit based on its position.

The key insight is to replace each ? with the largest possible digit while ensuring the overall time remains valid. This leads us to a greedy approach where we process each digit from left to right, considering the constraints imposed by adjacent digits.

Approach

  1. Hour First Digit (h1):

    • If h1 is ?, it can be either 2 if h2 is less than or equal to 3, otherwise, it should be 1.
  2. Hour Second Digit (h2):

    • If h2 is ?, it depends on the value of h1.
      • If h1 is 0 or 1, h2 can be 9.
      • If h1 is 2, h2 can be 3.
  3. Minute First Digit (m1):

    • If m1 is ?, it can be 5.
  4. Minute Second Digit (m2):

    • If m2 is ?, it can be 9.

By following these rules, we ensure that each digit is replaced with the largest possible value while maintaining a valid time.

Complexity Analysis

  • Time Complexity: O(1) since the length of the input string is fixed at 5 characters.
  • Space Complexity: O(1) as we are modifying the input string in place and using a constant amount of extra space.

Solution

def maximumTime(time: str) -> str:
    time = list(time)
    
    # Determine the first digit of the hour
    if time[0] == '?':
        time[0] = '2' if (time[1] == '?' or int(time[1]) <= 3) else '1'
    
    # Determine the second digit of the hour
    if time[1] == '?':
        time[1] = '3' if time[0] == '2' else '9'
    
    # Determine the first digit of the minute
    if time[3] == '?':
        time[3] = '5'
    
    # Determine the second digit of the minute
    if time[4] == '?':
        time[4] = '9'
    
    return ''.join(time)

Edge Cases Handled

  • All digits are hidden (????): The solution will return 23:59.
  • Only hour first digit is hidden (??:mm): The solution will replace it with the largest possible value based on the second hour digit.
  • Only hour second digit is hidden (h?:mm): The solution will replace it with the largest possible value based on the first hour digit.
  • Only minute first digit is hidden (hh:?m): The solution will replace it with 5.
  • Only minute second digit is hidden (hh:m?): The solution will replace it with 9.