3114. Latest Time You Can Obtain After Replacing Characters

SourceWeekly Contest 393 Q1DifficultyEasyRating1290

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

Thinking

There are only \(12\times 60\) valid times. Enumerating hour and minute from large to small and matching the pattern on non-? positions yields the latest feasible clock at the first hit.

The search space is constant, so backtracking is unnecessary. Walking from \(11{:}59\) down to \(00{:}00\) guarantees the lexicographically latest time.

Generate each HH:MM in that order, compare against \(s\) while treating ? as wild, and return the first match.

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

Thinking

Full enumeration is constant-time yet still formats hundreds of candidates. Each digit's range under the 12-hour clock can be written down directly.

The hour tens digit is \(0\) or \(1\), the ones digit is at most \(1\) when the tens digit is \(1\), the minute tens digit is at most \(5\), and the ones digit may be \(9\).

Replace each ? from left to right by the largest still-valid digit: decide \(s[0]\) then \(s[1]\), and fill the minute digits with \(5\) and \(9\). One pass suffices.

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

Python3JavaC++GoTypeScript

class Solution:
    def findLatestTime(self, s: str) -> str:
        s = list(s)
        if s[0] == "?":
            s[0] = "1" if s[1] == "?" or s[1] < "2" else "0"
        if s[1] == "?":
            s[1] = "1" if s[0] == "1" else "9"
        if s[3] == "?":
            s[3] = "5"
        if s[4] == "?":
            s[4] = "9"
        return "".join(s)

class Solution {
    public String findLatestTime(String s) {
        char[] cs = s.toCharArray();
        if (cs[0] == '?') {
            cs[0] = cs[1] == '?' || cs[1] < '2' ? '1' : '0';
        }
        if (cs[1] == '?') {
            cs[1] = cs[0] == '1' ? '1' : '9';
        }
        if (cs[3] == '?') {
            cs[3] = '5';
        }
        if (cs[4] == '?') {
            cs[4] = '9';
        }
        return new String(cs);
    }
}

class Solution {
public:
    string findLatestTime(string s) {
        if (s[0] == '?') {
            s[0] = s[1] == '?' || s[1] < '2' ? '1' : '0';
        }
        if (s[1] == '?') {
            s[1] = s[0] == '1' ? '1' : '9';
        }
        if (s[3] == '?') {
            s[3] = '5';
        }
        if (s[4] == '?') {
            s[4] = '9';
        }
        return s;
    }
};

func findLatestTime(s string) string {
    cs := []byte(s)
    if cs[0] == '?' {
        if cs[1] == '?' || cs[1] < '2' {
            cs[0] = '1'
        } else {
            cs[0] = '0'
        }
    }
    if cs[1] == '?' {
        if cs[0] == '1' {
            cs[1] = '1'
        } else {
            cs[1] = '9'
        }
    }
    if cs[3] == '?' {
        cs[3] = '5'
    }
    if cs[4] == '?' {
        cs[4] = '9'
    }
    return string(cs)
}

function findLatestTime(s: string): string {
    const cs = s.split('');
    if (cs[0] === '?') {
        cs[0] = cs[1] === '?' || cs[1] < '2' ? '1' : '0';
    }
    if (cs[1] === '?') {
        cs[1] = cs[0] === '1' ? '1' : '9';
    }
    if (cs[3] === '?') {
        cs[3] = '5';
    }
    if (cs[4] === '?') {
        cs[4] = '9';
    }
    return cs.join('');
}

3114. Latest Time You Can Obtain After Replacing Characters

Description

Solutions

Solution 1: Enumeration

Solution 2: Judge Each Digit

Comments