Latest Time You Can Obtain After Replacing Characters
EasyPrompt
You are given a string s representing a 12-hour format time where some of the digits (possibly none) are replaced with a "?".
12-hour times are formatted as "HH:MM", where HH is between 00 and 11, and MM is between 00 and 59. The earliest 12-hour time is 00:00, and the latest is 11:59.
You have to replace all the "?" characters in s with digits such that the time we obtain by the resulting string is a valid 12-hour format time and is the latest possible.
Return the resulting string.
Example 1:
Input: s = "1?:?4"
Output: "11:54"
Explanation: The latest 12-hour format time we can achieve by replacing "?" characters is "11:54".
Example 2:
Input: s = "0?:5?"
Output: "09:59"
Explanation: The latest 12-hour format time we can achieve by replacing "?" characters is "09:59".
Constraints:
s.length == 5s[2]is equal to the character":".- All characters except
s[2]are digits or"?"characters. - The input is generated such that there is at least one time between
"00:00"and"11:59"that you can obtain after replacing the"?"characters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores all possible ways to replace the '?' characters with digits from '0' to '9'. For each generated time string, it checks for validity (i.e., if it's a real time between 00:00 and 11:59). The latest valid time found among all possibilities is the answer.
Algorithm
- Create a recursive helper function
generate(char[] timeArray, int index). - The base case for the recursion is when
indexreaches the end of the array (index == 5). - In the base case, convert the character array to a string.
- Validate the generated time string. Check if HH is in [00, 11] and MM is in [00, 59].
- If it's a valid time, compare it with the
latestTimefound so far and update if the current time is later. - In the recursive step, if
timeArray[index]is a digit, simply callgenerate(timeArray, index + 1). - If
timeArray[index]is '?', loop through digits '0' to '9'. For each digit, place it attimeArray[index], recursively callgenerate(timeArray, index + 1), and then backtrack by resettingtimeArray[index]to '?'. - Initialize
latestTimeto an empty string and start the process by callinggeneratewith the initial time string and index 0.
Walkthrough
We can think of this as a search problem. The goal is to find the maximum valid time in the search space of all possible strings. A recursive function can be used to generate all combinations. The function would take the current index to fill and the partially built time string. When a '?' is encountered, the function recursively calls itself for each digit from '0' to '9'. When a full time string is formed (recursion reaches the end), we parse it and check if the hour is between 0 and 11 and the minute is between 0 and 59. We maintain a global or passed-down variable to keep track of the latest valid time seen so far. The base case for the recursion is when we have processed all characters of the string. Since the problem guarantees a solution exists, we will find at least one valid time.
class Solution { String latestTime = ""; public String maximumTime(String time) { char[] t = time.toCharArray(); generate(t, 0); return latestTime; } private void generate(char[] t, int index) { if (index == 5) { String currentTime = new String(t); if (isValid(currentTime)) { if (latestTime.isEmpty() || currentTime.compareTo(latestTime) > 0) { latestTime = currentTime; } } return; } if (t[index] == '?') { for (char c = '0'; c <= '9'; c++) { t[index] = c; generate(t, index + 1); t[index] = '?'; // backtrack } } else { generate(t, index + 1); } } private boolean isValid(String time) { try { int hh = Integer.parseInt(time.substring(0, 2)); int mm = Integer.parseInt(time.substring(3, 5)); return hh >= 0 && hh <= 11 && mm >= 0 && mm <= 59; } catch (NumberFormatException e) { return false; } }}Complexity
Time
O(1). Although the complexity is technically O(10^k) where k is the number of '?'s (k <= 4), the input size is fixed. The number of operations is constant but high, around 10^4 recursive calls in the worst case (`??:??`).
Space
O(1). The recursion depth is at most 5, which is constant. We also store the character array and the result string, both of constant size.
Trade-offs
Pros
Conceptually simple and guaranteed to find the correct answer by exploring all possibilities.
Cons
Highly inefficient. The number of combinations can be large (up to 10,000).
Performs many unnecessary checks for invalid times (e.g., '99:99').
A more direct approach is to check all possible valid times, starting from the latest possible (11:59) and working backwards to the earliest (00:00). The first time we find that matches the input pattern s must be the latest possible one.
Algorithm
- Loop through hours
hfrom 11 down to 0. - Inside this loop, loop through minutes
mfrom 59 down to 0. - For each pair
(h, m), create a candidate time string inHH:MMformat. - Compare this candidate string with the input pattern character by character.
- A character at a given position
iin the pattern matches the candidate ifpattern[i] == '?'orpattern[i] == candidate[i]. - If all characters match, the candidate is a possible time. Since we are iterating from latest to earliest, this is the latest possible time. Return it immediately.
- Since the problem guarantees a solution exists, the function will always return within the loops.
Walkthrough
This method avoids generating invalid times. We iterate through all 720 possible valid 12-hour times (12 hours * 60 minutes).
The loop can run from hour h = 11 down to 0, and for each hour, from minute m = 59 down to 0.
In each iteration, we format the current hour h and minute m into a HH:MM string. For example, if h=9 and m=5, the string is 09:05.
Then, we check if this candidate time string could be formed from the input s. A match occurs if for every character position, either the input has a '?' or the characters are identical.
The first time we find such a match, we have found our answer, and we can immediately return it.
class Solution { public String maximumTime(String time) { char[] pattern = time.toCharArray(); for (int h = 11; h >= 0; h--) { for (int m = 59; m >= 0; m--) { String candidate = String.format("%02d:%02d", h, m); if (matches(candidate, pattern)) { return candidate; } } } return ""; // Should not be reached based on problem constraints } private boolean matches(String candidate, char[] pattern) { for (int i = 0; i < 5; i++) { if (pattern[i] != '?' && pattern[i] != candidate.charAt(i)) { return false; } } return true; }}Complexity
Time
O(1). The loops run a fixed number of times (12 * 60 = 720). Each check is a constant time operation. The total number of operations is constant and significantly less than the brute-force approach.
Space
O(1). We only need space for the candidate string and the input pattern array, both of constant size.
Trade-offs
Pros
More efficient than brute force as it only checks valid times.
Still relatively simple to understand and implement.
Cons
In the worst case (e.g., input is
??:??and we need to find00:00, which is not the case here as we need latest), it might iterate through all 720 times.
The most efficient approach is to construct the latest time directly using a greedy strategy. We can determine the best possible digit for each '?' position by considering the constraints of the 12-hour format, aiming to maximize the time from left to right (hours first, then minutes).
Algorithm
- Convert the input string to a character array
tfor mutability. - Determine
t[0]: Ift[0]is '?', checkt[1]. Ift[1]is '?', '0', or '1', sett[0]to '1'. Otherwise, sett[0]to '0'. - Determine
t[1]: Ift[1]is '?', check the (possibly just updated)t[0]. Ift[0]is '1', sett[1]to '1'. Otherwise (t[0]is '0'), sett[1]to '9'. - Determine
t[3]: Ift[3]is '?', set it to '5'. - Determine
t[4]: Ift[4]is '?', set it to '9'. - Convert the modified character array back to a string and return it.
Walkthrough
To get the latest time, we must maximize the hour part first, then the minute part. This means we should make the digits from left to right as large as possible, while respecting the time format rules.
We can process the four digit positions (s[0], s[1], s[3], s[4]) one by one.
- For the hours (HH):
s[0](first hour digit): If it's '?', its value depends ons[1]. To maximize the hour, we prefer '1' over '0'. We can sets[0]to '1' only ifs[1]is '?', '0', or '1'. Otherwise,s[0]must be '0'.s[1](second hour digit): If it's '?', its value depends on the now-determineds[0]. Ifs[0]is '1', the latests[1]can be is '1' (for 11). Ifs[0]is '0', the latests[1]can be is '9' (for 09).
- For the minutes (MM):
s[3](first minute digit): If it's '?', the largest valid digit is '5' (for 5x minutes).s[4](second minute digit): If it's '?', the largest valid digit is '9'. This logic directly builds the final string in a single pass.
class Solution { public String maximumTime(String time) { char[] t = time.toCharArray(); // Handle HH if (t[0] == '?') { if (t[1] == '?' || t[1] <= '1') { t[0] = '1'; } else { t[0] = '0'; } } if (t[1] == '?') { if (t[0] == '1') { t[1] = '1'; } else { // t[0] == '0' t[1] = '9'; } } // Handle MM if (t[3] == '?') { t[3] = '5'; } if (t[4] == '?') { t[4] = '9'; } return new String(t); }}Complexity
Time
O(1). The algorithm performs a fixed number of checks and assignments, regardless of the input pattern. It's a single pass over a fixed-size string.
Space
O(1). A character array of size 5 is used, which is constant space.
Trade-offs
Pros
Extremely efficient with minimal operations.
Simple and elegant logic that directly solves the problem without searching.
Cons
Requires careful handling of the logic for the hour digits, as they are dependent on each other.
Solutions
Solution
class Solution {public String findLatestTime(String s) { for (int h = 11;; h--) { for (int m = 59; m >= 0; m--) { String t = String.format("%02d:%02d", h, m); boolean ok = true; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) != '?' && s.charAt(i) != t.charAt(i)) { ok = false; break; } } if (ok) { return t; } } } }}class Solution {public: string findLatestTime(string s) { for (int h = 11;; h--) { for (int m = 59; m >= 0; m--) { char t[6]; sprintf(t, "%02d:%02d", h, m); bool ok = true; for (int i = 0; i < s.length(); i++) { if (s[i] != '?' && s[i] != t[i]) { ok = false; break; } } if (ok) { return t; } } } }};class Solution: def findLatestTime(self, s: str) -> str: for h in range(11, - 1, - 1): for m in range(59, - 1, - 1): t = f " { h : 02 d } : { m : 02 d } " if all(a == b for a, b in zip(s, t) if a != "?"): return tVideo 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.