1736. Latest Time by Replacing Hidden Digits
Description
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 formathh:mm
.- It is guaranteed that you can produce a valid time from the given string.
Solutions
Solution 1: Greedy
We process each digit of the string in order, following these rules:
- First digit: If the value of the second digit is determined and falls within the range $[4, 9]$, then the first digit can only be $1$. Otherwise, the first digit can be up to $2$.
- Second digit: If the value of the first digit is determined and is $2$, then the second digit can be up to $3$. Otherwise, the second digit can be up to $9$.
- Third digit: The third digit can be up to $5$.
- Fourth digit: The fourth digit can be up to $9$.
The time complexity is $O(1)$, and the space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|