Latest Time by Replacing Hidden Digits
EasyPrompt
You are given a string time in the form of hh:mm, where some of the digits in the string are hidden (represented by ?).
The valid times are those inclusively between 00:00 and 23:59.
Return the latest valid time you can get from time by replacing the hidden digits.
Example 1:
Input: time = "2?:?0"
Output: "23:50"
Explanation: The latest hour beginning with the digit '2' is 23 and the latest minute ending with the digit '0' is 50.Example 2:
Input: time = "0?:3?"
Output: "09:39"Example 3:
Input: time = "1?:22"
Output: "19:22"
Constraints:
timeis in the formathh:mm.- It is guaranteed that you can produce a valid time from the given string.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through all possible valid times in a day, from the latest (23:59) to the earliest (00:00). For each time, we check if it can be formed from the input pattern. The first time that matches the pattern is the answer, as we are iterating downwards.
Algorithm
- Loop for
hourfrom 23 down to 0. - Inside this loop, loop for
minutefrom 59 down to 0. - Format the current
hourandminuteinto ahh:mmstring. For example, ifhouris 9 andminuteis 5, the string is "09:05". - Create a boolean flag
matchand set it totrue. - Compare this formatted time string with the input
timestring character by character. - A generated time is a "match" if for every position
i, eithergenerated_time[i] == input_time[i]orinput_time[i] == '?'. - If
matchis stilltrueafter all checks, we have found the latest possible time. Return the formatted time string.
Walkthrough
We can systematically check every minute of the day, starting from 23:59 and going down to 00:00. For each time (e.g., "23:59"), we create its string representation. We then compare this generated time string with the input time string character by character. A generated time is a "match" if for every position i from 0 to 4, either generated_time.charAt(i) == time.charAt(i) or time.charAt(i) == '?'. Since we are iterating from the latest possible time downwards, the very first match we find will be the latest valid time that can be formed. The problem guarantees that a valid time can always be produced, so we are sure to find a match.
class Solution { public String latestTimeByReplacingHiddenDigits(String time) { for (int h = 23; h >= 0; h--) { for (int m = 59; m >= 0; m--) { String currentTime = String.format("%02d:%02d", h, m); if (matches(currentTime, time)) { return currentTime; } } } return ""; // Should not be reached based on problem constraints } private boolean matches(String currentTime, String pattern) { for (int i = 0; i < 5; i++) { if (pattern.charAt(i) != '?' && pattern.charAt(i) != currentTime.charAt(i)) { return false; } } return true; }}Complexity
Time
O(1). The loops run a fixed number of times (24 * 60 = 1440). Inside the loop, the `matches` function and string formatting take constant time. The total number of operations is constant regardless of the input string's content (since its format is fixed).
Space
O(1). We only use a few variables to store the current time being checked.
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to be correct because it exhaustively checks all possibilities in the correct order.
Cons
Inefficient in terms of the number of operations. It performs up to 1440 iterations and comparisons, even though a direct solution is possible.
Solutions
Solution
class Solution {public String maximumTime(String time) { char[] t = time.toCharArray(); if (t[0] == '?') { t[0] = t[1] >= '4' && t[1] <= '9' ? '1' : '2'; } 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); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.