Latest Time by Replacing Hidden Digits

Easy
1186.

Latest Time by Replacing Hidden Digits

Latest Time by Replacing Hidden Digits is an easy coding problem on strings and greedy, asked in Amazon and Google interviews.

time is a 24-hour clock reading in the form hh:mm, but some of its digits are hidden and shown as '?'.

A valid time is any reading from 00:00 to 23:59 inclusive. Replace every '?' with a digit so that the result is a valid time, and return the latest valid time you can obtain, in the same hh:mm form. At least one valid replacement always exists.

Example 1

Input
time = "?4:5?"
Output
"14:59"
Explanation
With a 4 in the second hour digit the first one can be at most 1.

Example 2

Input
time = "1?:4?"
Output
"19:49"

Example 3

Input
time = "??:??"
Output
"23:59"

Constraints

  • time is in the format hh:mm
  • it is guaranteed that you can produce a valid time from the given string
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} time
 * @return {string}
 */
var maximumTime = function(time) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Latest Time by Replacing Hidden Digits — Problem & Solution

Latest Time by Replacing Hidden Digits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Latest Time by Replacing Hidden Digits is an easy coding problem on strings and greedy, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Strings, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

time is a 24-hour clock reading in the form hh:mm, but some of its digits are hidden and shown as '?'.

A valid time is any reading from 00:00 to 23:59 inclusive. Replace every '?' with a digit so that the result is a valid time, and return the latest valid time you can obtain, in the same hh:mm form. At least one valid replacement always exists.

Example 1

Input: time = "?4:5?"
Output: "14:59"
Explanation: With a 4 in the second hour digit the first one can be at most 1.

Example 2

Input: time = "1?:4?"
Output: "19:49"

Example 3

Input: time = "??:??"
Output: "23:59"

Constraints

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

Hints for Latest Time by Replacing Hidden Digits

  1. Hint 1

    Fill the digits from left to right — an earlier digit matters more than all later ones.

  2. Hint 2

    The minute digits are independent of everything else: 5 and 9 are always allowed.

  3. Hint 3

    For the hours: the first digit can be 2 only if the second is hidden or at most 3; the second digit can be 9 unless the first is 2, in which case it is 3.

How to solve Latest Time by Replacing Hidden Digits

Comparing two times is comparing their digits left to right, so greedily give each hidden digit the largest value that still allows a valid time, starting from the most significant position.

Approach

  1. If h0 is hidden: set it to 2 when h1 is hidden or h1 <= '3', otherwise to 1.
  2. If h1 is hidden: set it to 3 when h0 is 2, otherwise to 9.
  3. If m0 is hidden, set it to 5; if m1 is hidden, set it to 9.
  4. Return the filled string.

Why it works

Hours run up to 23, so h0 can be 2 only if the second digit can still be 0–3 — true when it is hidden (we will choose 3) or already at most 3. Once h0 is fixed, the largest legal h1 is 3 after a 2 and 9 after a 0 or 1. Minutes go up to 59 independently. Each choice is the maximum that keeps a completion possible, and earlier digits dominate later ones, so the result is the latest time.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • Decide h0 before h1, but look at the original h1 when deciding h0.
  • "?4:00" must become 14:00, not 24:00.
  • "2?:.." allows at most 23, not 29.

Reference solution

Python

def maximumTime(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)

Java

public static String maximumTime(String time) {
    char[] t = time.toCharArray();
    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 new String(t);
}

C++

string maximumTime(string time) {
    string t = time;
    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;
}

JavaScript

var maximumTime = function(time) {
    var 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("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms