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 == 5s[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
Hint 1
Fill the positions from left to right — a larger digit earlier always beats anything later.
Hint 2
The first hour digit can be
1only if the second hour digit is?or at most1; otherwise it must be0.Hint 3
The second hour digit is
1after a1, else9. Minutes are simply5then9.
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
- If
s[0]is?: it becomes1whens[1]is?or<= '1', and0otherwise. - If
s[1]is?: it becomes1whens[0]is1, and9otherwise. - If
s[3]is?it becomes5; ifs[4]is?it becomes9.
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
1in 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