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)\).

Python3JavaC++GoTypeScript

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

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;
                }
            }
        }
    }
};

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;
            }
        }
    }
}

Solution 2: Judge Each Digit

We can judge each digit of \(s\) one by one. If it is "?", we determine the value of this digit based on the characters before and after it. Specifically, we have the following rules:

If \(s[0]\) is "?", then the value of \(s[0]\) should be "1" or "0", depending on the value of \(s[1]\). If \(s[1]\) is "?" or \(s[1]\) is less than "2", then the value of \(s[0]\) should be "1", otherwise the value of \(s[0]\) should be "0".
If \(s[1]\) is "?", then the value of \(s[1]\) should be "1" or "9", depending on the value of \(s[0]\). If \(s[0]\) is "1", then the value of \(s[1]\) should be "1", otherwise the value of \(s[1]\) should be "9".
If \(s[3]\) is "?", then the value of \(s[3]\) should be "5".
If \(s[4]\) is "?", then the value of \(s[4]\) should be "9".

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).