# 3114. Latest Time You Can Obtain After Replacing Characters

## Description

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 == 5
• s[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.

## Solutions

### Solution 1: Enumeration

We can enumerate all times from large to small, where the hour $h$ ranges from $11$ to $0$, and the minute $m$ ranges from $59$ to $0$. For each time $t$, we check whether each digit of $t$ matches the corresponding digit in $s$ (if the corresponding digit in $s$ is not “?”). If it does, then we have found the answer and return $t$.

The time complexity is $O(h \times m)$, where $h = 12$ and $m = 60$. The space complexity is $O(1)$.

• 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:02d}:{m:02d}"
if all(a == b for a, b in zip(s, t) if a != "?"):
return t


• func findLatestTime(s string) string {
for h := 11; ; h-- {
for m := 59; m >= 0; m-- {
t := fmt.Sprintf("%02d:%02d", h, m)
ok := true
for i := 0; i < len(s); i++ {
if s[i] != '?' && s[i] != t[i] {
ok = false
break
}
}
if ok {
return t
}
}
}
}

• function findLatestTime(s: string): string {
for (let h = 11; ; h--) {
for (let m = 59; m >= 0; m--) {
const t: string = ${h.toString().padStart(2, '0')}:${m.toString().padStart(2, '0')};
let ok: boolean = true;
for (let i = 0; i < s.length; i++) {
if (s[i] !== '?' && s[i] !== t[i]) {
ok = false;
break;
}
}
if (ok) {
return t;
}
}
}
}