#1736

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Latest Time by Replacing Hidden Digits

Determine the latest valid time by replacing hidden digits using a greedy choice and invariant validation strategy efficiently.

string greedy

Problem Statement

Given a string representing time in the format hh:mm, some digits may be hidden as '?'. Your goal is to replace each '?' with a digit to form the latest valid 24-hour time possible.

A valid time is any time from 00:00 to 23:59. Return the resulting string after replacing all hidden digits to achieve the maximum possible time, adhering to the hh:mm format.

Examples

Example 1

Input: time = "2?:?0"

Output: "23:50"

The latest hour beginning with the digit '2' is 23 and the latest minute ending with the digit '0' is 50.

Example 2

Input: time = "0?:3?"

Output: "09:39"

Example details omitted.

Example 3

Input: time = "1?:22"

Output: "19:22"

Example details omitted.

Constraints

time is in the format hh:mm.
It is guaranteed that you can produce a valid time from the given string.

Solution Approach

Greedy Replacement by Position

Analyze each position in hh:mm starting from the most significant digit. Choose the largest digit that keeps the hour and minute within valid bounds. For example, if the first hour digit is '?', pick '2' if possible, otherwise '1' or '0'.

Invariant Validation

At each replacement, ensure the partially constructed time can still become valid. Avoid choosing digits that force an invalid time later, such as selecting '3' for the first hour digit when the second digit cannot form a number less than 4.

Construct Final Time

After greedy replacement with invariant checks, combine the chosen digits to produce the final string. This ensures the latest time while respecting all hidden digits and hh:mm format constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(1) since the string has a fixed length of 5 characters, and each '?' requires at most a few constant checks. Space complexity is O(1) as only a few variables are needed for construction.

What Interviewers Usually Probe

Identifying that a brute-force solution is unnecessary due to the fixed-length string.
Recognizing the pattern as greedy plus invariant validation.
Expecting careful digit-by-digit reasoning to avoid invalid hours or minutes.

Common Pitfalls or Variants

Common pitfalls

Choosing the largest digit without validating the resulting time, which may produce an invalid hour or minute.
Ignoring the dependency between the first and second hour digits when the first is '2'.
Overcomplicating by attempting full enumeration instead of greedy choice.

Follow-up variants

Maximize the earliest valid time instead of the latest by reversing greedy choices.
Handle a 12-hour format with hidden digits and AM/PM markers.
Replace hidden digits in a larger timestamp string including seconds.

FAQ

How do I handle the first digit being '?' in 'Latest Time by Replacing Hidden Digits'?

Replace '?' with the largest valid digit that allows the second hour digit to stay within 0-3 if the first digit is '2', otherwise choose '0' or '1' as needed.

Can this problem be solved by brute-force enumeration?

Yes, but brute-force is unnecessary; greedy replacement with invariant validation achieves O(1) complexity due to the fixed string length.

What if both hour digits are '?'?

Start by setting the first to '2' if possible, then adjust the second to the highest digit that forms a valid hour, following greedy invariant rules.

How do I handle the minute digits when they contain '?'?

Greedily choose '5' for the first minute digit and '9' for the second unless constrained by the input pattern.

Does this problem pattern apply to other string replacement problems?

Yes, it follows a greedy plus invariant validation pattern suitable for constructing maximum or minimum valid values in constrained string formats.

terminal

Solution

Solution 1: Greedy

We process each digit of the string in order, following these rules:

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#1754 largest merge of two strings #1717 maximum score from removing substrings #1702 maximum binary string after change