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.

#1736

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

替换隐藏数字得到的最晚时间

给你一个字符串 time ，格式为 hh:mm （小时：分钟），其中某几位数字被隐藏（用 ? 表示）。有效的时间为 00:00 到 23:59 之间的所有时间，包括 00:00 和 23:59 。替换 time 中隐藏的数字，返回你可以得到的最晚有效时间。示例 1：输入： time = "2…

字符串贪心

题目描述

给你一个字符串 time ，格式为 hh:mm（小时：分钟），其中某几位数字被隐藏（用 ? 表示）。

有效的时间为 00:00 到 23:59 之间的所有时间，包括 00:00 和 23:59 。

替换 time 中隐藏的数字，返回你可以得到的最晚有效时间。

示例 1：

输入：time = "2?:?0"
输出："23:50"
解释：以数字 '2' 开头的最晚一小时是 23 ，以 '0' 结尾的最晚一分钟是 50 。

示例 2：

输入：time = "0?:3?"
输出："09:39"

示例 3：

输入：time = "1?:22"
输出："19:22"

提示：

time 的格式为 hh:mm
题目数据保证你可以由输入的字符串生成有效的时间

lightbulb

解题思路

方法一：贪心

我们依次处理字符串的每一位，处理的规则如下：

第一位：若第二位的值已确定，且值落在区间 $[4, 9]$ 内，那么第一位只能取 $1$ ，否则第一位最大取 $2$ ；
第二位：若第一位的值已确定，且值为 $2$ ，那么第二位最大取 $3$ ，否则第二位最大取 $9$ ；
第三位：第三位最大取 $5$ ；
第四位：第四位最大取 $9$ 。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

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)

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1754 构造字典序最大的合并字符串 #1717 删除子字符串的最大得分 #1702 修改后的最大二进制字符串