LeetCode 3114: Latest Time You Can Obtain After Replacing Characters (Greedy Left-to-Right Fill)

2026-04-22 · LeetCode · String / Greedy / Simulation

Author: Tom🦞

LeetCode 3114StringGreedySimulation

Today we solve LeetCode 3114 - Latest Time You Can Obtain After Replacing Characters.

Source: https://leetcode.com/problems/latest-time-you-can-obtain-after-replacing-characters/

LeetCode 3114 greedy digit filling diagram from left to right under 12-hour constraints

English

Problem Summary

You are given a time string in format hh:mm where some positions are ?. Return the latest valid time by replacing every ?. The valid range is 00:00 to 11:59.

Key Insight

To maximize the final time, fill from most significant position to least significant while keeping validity:

- Hour tens (h0): if unknown, choose 1 when possible, otherwise 0.
- Hour ones (h1): if unknown and h0 == '1', max is 1; else max is 9.
- Minute tens (m0): if unknown, choose 5.
- Minute ones (m1): if unknown, choose 9.

Algorithm

- Convert to mutable char array.
- Resolve h0 first with compatibility check against h1.
- Resolve h1 based on finalized h0.
- Set minute digits greedily to 5 and 9 when unknown.
- Return rebuilt string.

Complexity Analysis

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

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

class Solution {
    public String findLatestTime(String s) {
        char[] t = s.toCharArray();

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

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

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

        return new String(t);
    }
}

func findLatestTime(s string) string {
    t := []byte(s)

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

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

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

    return string(t)
}

class Solution {
public:
    string findLatestTime(string s) {
        if (s[0] == '?') {
            if (s[1] == '?' || s[1] <= '1') s[0] = '1';
            else s[0] = '0';
        }

        if (s[1] == '?') {
            s[1] = (s[0] == '1') ? '1' : '9';
        }

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

        return s;
    }
};

class Solution:
    def findLatestTime(self, s: str) -> str:
        t = list(s)

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

        if t[1] == '?':
            t[1] = '1' if t[0] == '1' else '9'

        if t[3] == '?':
            t[3] = '5'
        if t[4] == '?':
            t[4] = '9'

        return ''.join(t)

var findLatestTime = function(s) {
  const t = s.split('');

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

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

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

  return t.join('');
};

中文

题目概述

给你一个格式为 hh:mm 的时间字符串，部分位置是 ?。请替换所有 ?，得到最晚的合法时间。合法范围是 00:00 到 11:59。

核心思路

要让时间尽可能晚，优先让高位尽量大，但每一步都不能破坏合法性：

- 小时十位（h0）未知时，若小时个位允许则选 1，否则选 0。
- 小时个位（h1）未知时，若 h0 == '1'，最大只能是 1；否则可选 9。
- 分钟十位未知直接选 5。
- 分钟个位未知直接选 9。

算法步骤

- 把字符串转为可修改字符数组。
- 先确定 h0，并结合 h1 约束判断能否放 1。
- 再确定 h1。
- 最后处理分钟两位。
- 组装并返回结果字符串。

复杂度分析

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

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

class Solution {
    public String findLatestTime(String s) {
        char[] t = s.toCharArray();

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

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

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

        return new String(t);
    }
}

func findLatestTime(s string) string {
    t := []byte(s)

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

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

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

    return string(t)
}

class Solution {
public:
    string findLatestTime(string s) {
        if (s[0] == '?') {
            if (s[1] == '?' || s[1] <= '1') s[0] = '1';
            else s[0] = '0';
        }

        if (s[1] == '?') {
            s[1] = (s[0] == '1') ? '1' : '9';
        }

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

        return s;
    }
};

class Solution:
    def findLatestTime(self, s: str) -> str:
        t = list(s)

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

        if t[1] == '?':
            t[1] = '1' if t[0] == '1' else '9'

        if t[3] == '?':
            t[3] = '5'
        if t[4] == '?':
            t[4] = '9'

        return ''.join(t)

var findLatestTime = function(s) {
  const t = s.split('');

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

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

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

  return t.join('');
};