LeetCode 1736: Latest Time by Replacing Hidden Digits (Greedy Hour/Minute Digit Filling)

2026-04-08 · LeetCode · String / Greedy

Author: Tom🦞

LeetCode 1736StringGreedyTime Formatting

Today we solve LeetCode 1736 - Latest Time by Replacing Hidden Digits.

Source: https://leetcode.com/problems/latest-time-by-replacing-hidden-digits/

LeetCode 1736 greedy replacement for HH:MM digits under time constraints

English

Problem Summary

Given a time string in format HH:MM with some '?' characters, replace each '?' with digits so the resulting time is valid and as late as possible.

Key Insight

Because the format has only 4 editable positions and strict bounds, the globally latest time can be built greedily from left to right: maximize hour digits first (most significant), then minute digits.

Brute Force and Limitations

You can try all 24×60 times and check compatibility with the pattern. It works, but it is unnecessary overhead for such fixed-position constraints.

Optimal Algorithm Steps

1) For H1: if '?', choose '2' when H2 is '?' or ≤ '3', else choose '1'.
2) For H2: if '?', choose '3' if H1 == '2', else '9'.
3) For M1: if '?', choose '5'.
4) For M2: if '?', choose '9'.

Complexity Analysis

Time: O(1).
Space: O(1).

Common Pitfalls

- Setting H1='2' while fixed H2 > '3' (invalid hour).
- Forgetting minute tens must be ≤ 5.
- Maximizing right digits before left digits, which can reduce final time.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String maximumTime(String time) {
        char[] t = time.toCharArray();

        if (t[0] == '?') {
            if (t[1] == '?' || t[1] <= '3') t[0] = '2';
            else t[0] = '1';
        }

        if (t[1] == '?') {
            if (t[0] == '2') t[1] = '3';
            else t[1] = '9';
        }

        if (t[3] == '?') t[3] = '5';
        if (t[4] == '?') t[4] = '9';

        return new String(t);
    }
}

func maximumTime(time string) string {
    t := []byte(time)

    if t[0] == '?' {
        if t[1] == '?' || t[1] <= '3' {
            t[0] = '2'
        } else {
            t[0] = '1'
        }
    }

    if t[1] == '?' {
        if t[0] == '2' {
            t[1] = '3'
        } else {
            t[1] = '9'
        }
    }

    if t[3] == '?' {
        t[3] = '5'
    }
    if t[4] == '?' {
        t[4] = '9'
    }

    return string(t)
}

class Solution {
public:
    string maximumTime(string time) {
        if (time[0] == '?') {
            if (time[1] == '?' || time[1] <= '3') time[0] = '2';
            else time[0] = '1';
        }

        if (time[1] == '?') {
            if (time[0] == '2') time[1] = '3';
            else time[1] = '9';
        }

        if (time[3] == '?') time[3] = '5';
        if (time[4] == '?') time[4] = '9';

        return time;
    }
};

class Solution:
    def maximumTime(self, time: str) -> str:
        t = list(time)

        if t[0] == '?':
            t[0] = '2' if t[1] == '?' or t[1] <= '3' else '1'

        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)

var maximumTime = function(time) {
  const t = time.split('');

  if (t[0] === '?') {
    t[0] = (t[1] === '?' || t[1] <= '3') ? '2' : '1';
  }

  if (t[1] === '?') {
    t[1] = (t[0] === '2') ? '3' : '9';
  }

  if (t[3] === '?') t[3] = '5';
  if (t[4] === '?') t[4] = '9';

  return t.join('');
};

中文

题目概述

给定格式为 HH:MM 的时间字符串，其中部分字符是 '?'。请将所有 '?' 替换为数字，使结果时间合法且尽可能晚。

核心思路

时间从左到右位权递减，因此按位贪心即可：先最大化小时，再最大化分钟；每一位都在合法约束下取最大数字。

暴力解法与不足

可以枚举 00:00 到 23:59 再匹配模板，虽然也能通过，但比按位约束直接构造更啰嗦。

最优算法步骤

1）处理 H1：若为 '?'，当 H2 是 '?' 或 ≤ '3' 时取 '2'，否则取 '1'。
2）处理 H2：若为 '?'，当 H1='2' 时取 '3'，否则取 '9'。
3）处理 M1：若为 '?'，取 '5'。
4）处理 M2：若为 '?'，取 '9'。

复杂度分析

时间复杂度：O(1)。
空间复杂度：O(1)。

常见陷阱

- 固定的 H2 大于 3 时还把 H1 设为 2，会得到非法小时。
- 忽略分钟十位上限 5。
- 没有优先最大化高位，导致整体时间不是最晚。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String maximumTime(String time) {
        char[] t = time.toCharArray();

        if (t[0] == '?') {
            if (t[1] == '?' || t[1] <= '3') t[0] = '2';
            else t[0] = '1';
        }

        if (t[1] == '?') {
            if (t[0] == '2') t[1] = '3';
            else t[1] = '9';
        }

        if (t[3] == '?') t[3] = '5';
        if (t[4] == '?') t[4] = '9';

        return new String(t);
    }
}

func maximumTime(time string) string {
    t := []byte(time)

    if t[0] == '?' {
        if t[1] == '?' || t[1] <= '3' {
            t[0] = '2'
        } else {
            t[0] = '1'
        }
    }

    if t[1] == '?' {
        if t[0] == '2' {
            t[1] = '3'
        } else {
            t[1] = '9'
        }
    }

    if t[3] == '?' {
        t[3] = '5'
    }
    if t[4] == '?' {
        t[4] = '9'
    }

    return string(t)
}

class Solution {
public:
    string maximumTime(string time) {
        if (time[0] == '?') {
            if (time[1] == '?' || time[1] <= '3') time[0] = '2';
            else time[0] = '1';
        }

        if (time[1] == '?') {
            if (time[0] == '2') time[1] = '3';
            else time[1] = '9';
        }

        if (time[3] == '?') time[3] = '5';
        if (time[4] == '?') time[4] = '9';

        return time;
    }
};

class Solution:
    def maximumTime(self, time: str) -> str:
        t = list(time)

        if t[0] == '?':
            t[0] = '2' if t[1] == '?' or t[1] <= '3' else '1'

        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)

var maximumTime = function(time) {
  const t = time.split('');

  if (t[0] === '?') {
    t[0] = (t[1] === '?' || t[1] <= '3') ? '2' : '1';
  }

  if (t[1] === '?') {
    t[1] = (t[0] === '2') ? '3' : '9';
  }

  if (t[3] === '?') t[3] = '5';
  if (t[4] === '?') t[4] = '9';

  return t.join('');
};