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:mmit is guaranteed that you can produce a valid time from the given string
Hints for Latest Time by Replacing Hidden Digits
Hint 1
Fill the digits from left to right — an earlier digit matters more than all later ones.
Hint 2
The minute digits are independent of everything else:
5and9are always allowed.Hint 3
For the hours: the first digit can be
2only if the second is hidden or at most3; the second digit can be9unless the first is2, in which case it is3.
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
- If
h0is hidden: set it to2whenh1is hidden orh1 <= '3', otherwise to1. - If
h1is hidden: set it to3whenh0is2, otherwise to9. - If
m0is hidden, set it to5; ifm1is hidden, set it to9. - 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
h0beforeh1, but look at the originalh1when decidingh0. "?4:00"must become14:00, not24:00."2?:.."allows at most23, not29.
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