Latest Time You Can Obtain After Replacing Characters

Easy
1768.

Latest Time You Can Obtain After Replacing Characters

Latest Time You Can Obtain After Replacing Characters is an easy coding problem on strings and enumeration, asked in Amazon and Microsoft interviews.

You are given a string s describing a 12-hour clock reading in the format "HH:MM", where some digits have been replaced by '?'. A valid reading has HH between 00 and 11 and MM between 00 and 59; the earliest is 00:00 and the latest is 11:59.

Replace every '?' with a digit so that the result is a valid time and is as late as possible. Return the resulting string.

The input is guaranteed to allow at least one valid time.

Example 1

Input
s = "1?:?4"
Output
11:54
Explanation
The hour can be at most 11, and with the last digit fixed at 4 the latest minute is 54.

Example 2

Input
s = "0?:5?"
Output
09:59
Explanation
An hour starting with 0 can reach 09.

Example 3

Input
s = "??:??"
Output
11:59

Constraints

  • s.length == 5
  • s[2] == ':'
  • every other character of s is a digit or '?'
  • at least one valid time between 00:00 and 11:59 can be produced
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} s
 * @return {string}
 */
var findLatestTime = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Latest Time You Can Obtain After Replacing Characters Solution

Latest Time You Can Obtain After Replacing Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Latest Time You Can Obtain After Replacing Characters is an easy coding problem on strings and enumeration, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Strings, Enumeration
  • Asked at: Amazon, Microsoft
  • 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

You are given a string s describing a 12-hour clock reading in the format "HH:MM", where some digits have been replaced by '?'. A valid reading has HH between 00 and 11 and MM between 00 and 59; the earliest is 00:00 and the latest is 11:59.

Replace every '?' with a digit so that the result is a valid time and is as late as possible. Return the resulting string.

The input is guaranteed to allow at least one valid time.

Example 1

Input: s = "1?:?4"
Output: 11:54
Explanation: The hour can be at most 11, and with the last digit fixed at 4 the latest minute is 54.

Example 2

Input: s = "0?:5?"
Output: 09:59
Explanation: An hour starting with 0 can reach 09.

Example 3

Input: s = "??:??"
Output: 11:59

Constraints

  • s.length == 5
  • s[2] == ':'
  • every other character of s is a digit or '?'
  • at least one valid time between 00:00 and 11:59 can be produced

Hints for Latest Time You Can Obtain After Replacing Characters

  1. Hint 1

    Fill the positions from left to right — a larger digit earlier always beats anything later.

  2. Hint 2

    The first hour digit can be 1 only if the second hour digit is ? or at most 1; otherwise it must be 0.

  3. Hint 3

    The second hour digit is 1 after a 1, else 9. Minutes are simply 5 then 9.

How to solve Latest Time You Can Obtain After Replacing Characters

Times compare like strings of the same shape, so the latest time is found greedily: give each ? the largest digit that still leaves a valid time, from the most significant position to the least.

Approach

  1. If s[0] is ?: it becomes 1 when s[1] is ? or <= '1', and 0 otherwise.
  2. If s[1] is ?: it becomes 1 when s[0] is 1, and 9 otherwise.
  3. If s[3] is ? it becomes 5; if s[4] is ? it becomes 9.

Why it works

Hour 1x is only valid for x in {0, 1}, so s[0] = '1' is possible exactly when s[1] allows 0 or 1, and it is always better than 0. Given the first hour digit, the largest allowed second digit is 1 or 9. The minutes are independent of the hour and are maximised by 59.

Complexity

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

Pitfalls

  • "?9:.." must become "09" — a greedy 1 in front would make the invalid hour 19.
  • This is a 12-hour clock: the latest hour is 11, not 23.

Reference solution

Python

def findLatestTime(s: str) -> str:
    t = list(s)
    if t[0] == "?":
        t[0] = "1" if t[1] == "?" or t[1] <= "1" else "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)

Java

public static String findLatestTime(String s) {
    char[] t = s.toCharArray();
    if (t[0] == '?') t[0] = (t[1] == '?' || t[1] <= '1') ? '1' : '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);
}

C++

string findLatestTime(string s) {
    if (s[0] == '?') s[0] = (s[1] == '?' || s[1] <= '1') ? '1' : '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;
}

JavaScript

var findLatestTime = function(s) {
    var t = s.split("");
    if (t[0] === "?") t[0] = (t[1] === "?" || t[1] <= "1") ? "1" : "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("");
};

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