Teaching Kids Programming – Latest Time You Can Obtain After Replacing Characters (Decision Tree)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Hints:
Try using a brute force approach.
Iterate over all possible times that can be generated from the string and find the latest one.

Latest Time You Can Obtain After Replacing Characters (Decision Tree)

We can check each hidden digit and make decision. For the minutes, if digits are hidden, we can easily replace them with either 5 or 9. For the hours, we need to check another digit, but this is trivial as well. The whole algorithm is decision tree where we can solve this problem using simple if-else checks.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

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

The time/space complexity is O(1) since this problem is bounded e.g. there is only 5 character string.

–EOF (The Ultimate Computing & Technology Blog) —