Latest Time by Replacing Hidden Digits

Easy

#1590Time: 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.

Patterns

Greedy

Data structures

String

Prompt

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:

time is in the format hh: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 hour from 23 down to 0.
Inside this loop, loop for minute from 59 down to 0.
Format the current hour and minute into a hh:mm string. For example, if hour is 9 and minute is 5, the string is "09:05".
Create a boolean flag match and set it to true.
Compare this formatted time string with the input time string character by character.
A generated time is a "match" if for every position i, either generated_time[i] == input_time[i] or input_time[i] == '?'.
If match is still true after 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.

1class Solution {2    public String latestTimeByReplacingHiddenDigits(String time) {3        for (int h = 23; h >= 0; h--) {4            for (int m = 59; m >= 0; m--) {5                String currentTime = String.format("%02d:%02d", h, m);6                if (matches(currentTime, time)) {7                    return currentTime;8                }9            }10        }11        return ""; // Should not be reached based on problem constraints12    }13 14    private boolean matches(String currentTime, String pattern) {15        for (int i = 0; i < 5; i++) {16            if (pattern.charAt(i) != '?' && pattern.charAt(i) != currentTime.charAt(i)) {17                return false;18            }19        }20        return true;21    }22}

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.

A more efficient approach is to construct the latest time directly using a greedy strategy. We fill in the '?' characters from left to right (most significant digit to least significant) with the largest possible valid values.

Algorithm

Convert the input time string into a character array t.
Handle t[0] (first hour digit):
- If t[0] == '?':
  - If t[1] == '?' or t[1] <= '3', set t[0] = '2'.
  - Else, set t[0] = '1'.
Handle t[1] (second hour digit):
- If t[1] == '?':
  - If t[0] == '2', set t[1] = '3'.
  - Else, set t[1] = '9'.
Handle t[3] (first minute digit):
- If t[3] == '?', set t[3] = '5'.
Handle t[4] (second minute digit):
- If t[4] == '?', set t[4] = '9'.
Convert the character array t back to a string and return it.

Walkthrough

To get the latest time, we want to maximize the hour first, and then the minute. This means we should try to make the digits h1, h2, m1, m2 as large as possible, in that order of priority. We can convert the input string to a character array to modify it in place.

Hour:

For the first hour digit (time[0]): If it's a '?', its value depends on the second digit (time[1]). To maximize the hour, we want to use '2' if possible. This is possible if time[1] is '?', '0', '1', '2', or '3'. If time[1] is '4' or greater, the first digit can't be '2' (as 24 is an invalid hour), so it must be '1'.
For the second hour digit (time[1]): If it's a '?', its value depends on the first digit (time[0]). If time[0] is '2', the latest time[1] can be is '3'. If time[0] is '0' or '1', the latest time[1] can be is '9'.

Minute:

For the first minute digit (time[3]): If it's a '?', the largest valid digit is '5' (to form minutes 50-59).
For the second minute digit (time[4]): If it's a '?', the largest valid digit is '9'.

After filling all '?'s based on these rules, we convert the character array back to a string.

1class Solution {2    public String latestTimeByReplacingHiddenDigits(String time) {3        char[] t = time.toCharArray();4 5        // Handle hour6        if (t[0] == '?') {7            if (t[1] == '?' || t[1] <= '3') {8                t[0] = '2';9            } else {10                t[0] = '1';11            }12        }13        if (t[1] == '?') {14            if (t[0] == '2') {15                t[1] = '3';16            } else {17                t[1] = '9';18            }19        }20 21        // Handle minute22        if (t[3] == '?') {23            t[3] = '5';24        }25        if (t[4] == '?') {26            t[4] = '9';27        }28 29        return new String(t);30    }31}

Complexity

Time

O(1). We perform a single pass over the 5 characters of the string. The number of operations is constant.

Space

O(1). We use a character array of a fixed size (5) to build the result.

Trade-offs

Pros

Extremely efficient with a minimal number of operations.
Directly constructs the result without unnecessary iterations or checks.

Cons

The logic involves several conditional checks which can be tricky to get right on the first try.

Solutions

Solution

1class Solution {2public3  String maximumTime(String time) {4    char[] t = time.toCharArray();5    if (t[0] == '?') {6      t[0] = t[1] >= '4' && t[1] <= '9' ? '1' : '2';7    }8    if (t[1] == '?') {9      t[1] = t[0] == '2' ? '3' : '9';10    }11    if (t[3] == '?') {12      t[3] = '5';13    }14    if (t[4] == '?') {15      t[4] = '9';16    }17    return new String(t);18  }19}

1/** * @param {string} time * @return {string} */ var maximumTime = function (2  time,3) {4  const t = Array.from(time);5  if (t[0] === " ? ") {6    t[0] = t[1] >= " 4 " && t[1] <= " 9 " ? " 1 " : " 2 ";7  }8  if (t[1] === " ? ") {9    t[1] = t[0] == " 2 " ? " 3 " : " 9 ";10  }11  if (t[3] === " ? ") {12    t[3] = " 5 ";13  }14  if (t[4] === " ? ") {15    t[4] = " 9 ";16  }17  return t.join("");18};

1class Solution {2public:3  string maximumTime(string time) {4    if (time[0] == '?') {5      time[0] = (time[1] >= '4' && time[1] <= '9') ? '1' : '2';6    }7    if (time[1] == '?') {8      time[1] = (time[0] == '2') ? '3' : '9';9    }10    if (time[3] == '?') {11      time[3] = '5';12    }13    if (time[4] == '?') {14      time[4] = '9';15    }16    return time;17  }18};

1class Solution:2    def maximumTime(self, time: str) -> str: t = list(time) if t[0] == '?': t[0] = '1' if '4' <= t[1] <= '9' else '2' 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)

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.

← Previous

Previous problem

Next problem