Leetcode 1736. Latest Time by Replacing Hidden Digits

Problem Explanation

In this problem, you are given a time string in the format hh:mm where some digits might be hidden (represented by a question mark "?"). Your task is to determine the latest valid time you can get by replacing the hidden digits. The valid times are those between 00:00 and 23:59, inclusive.

Let's walk through an example to understand the problem better:

Example:

Input: time = "1?:22"

1. The first hidden digit is in the hours part. Since it starts with '1', the latest hour we can get is 19 (as the first digit can be between 0 to 2, and the second digit can be between 0 to 3 if the first digit is 2, and 0 to 9 if the first digit is 0 or 1).
2. There is no hidden digit in the minutes part. So the minute stays as '22'.
3. Therefore, the latest valid time by replacing the hidden digit is "19:22".

Solution Approach

The solution to this problem can be achieved through simple condition checking for each digit of the input string. We will replace the hidden digits with the maximum possible value according to the given rules.

1. Check if the first digit is hidden:
   • If it is hidden, replace it with 2 if the second digit is less than or equal to 3, else, replace it with 1.
   • If it is not hidden, do nothing.
2. Check if the second digit is hidden:
   • If it is hidden, replace it with 9 if the first digit is less than or equal to 1, else, replace it with 3.
   • If it is not hidden, do nothing.
3. Check if the fourth digit is hidden:
   • If it is hidden, replace it with 5.
   • If it is not hidden, do nothing.
4. Check if the fifth digit is hidden:
   • If it is hidden, replace it with 9.
   • If it is not hidden, do nothing.

Python Solution

1class Solution:
2    def maximumTime(self, time: str) -> str:
3        ans = list(time)
4
5        if ans[0] == '?' or ans[1] == '?':
6            if ans[0] == '?':
7                ans[0] = '2' if ans[1] <= '3' or ans[1] == '?' else '1'
8            if ans[1] == '?':
9                ans[1] = '9' if ans[0] <= '1' else '3'
10
11        if ans[3] == '?':
12            ans[3] = '5'
13
14        if ans[4] == '?':
15            ans[4] = '9'
16
17        return ''.join(ans)

Java Solution

1class Solution {
2    public String maximumTime(String time) {
3        char[] ans = time.toCharArray();
4
5        if (ans[0] == '?' || ans[1] == '?') {
6            if (ans[0] == '?') {
7                ans[0] = (ans[1] <= '3' || ans[1] == '?') ? '2' : '1';
8            }
9            if (ans[1] == '?') {
10                ans[1] = (ans[0] <= '1') ? '9' : '3';
11            }
12        }
13
14        if (ans[3] == '?') {
15            ans[3] = '5';
16        }
17
18        if (ans[4] == '?') {
19            ans[4] = '9';
20        }
21
22        return new String(ans);
23    }
24}

JavaScript Solution

1class Solution {
2    maximumTime(time) {
3        let ans = time.split('');
4
5        if (ans[0] === '?' || ans[1] === '?') {
6            if (ans[0] === '?') {
7                ans[0] = (ans[1] <= '3' || ans[1] === '?') ? '2' : '1';
8            }
9            if (ans[1] === '?') {
10                ans[1] = (ans[0] <= '1') ? '9' : '3';
11            }
12        }
13
14        if (ans[3] === '?') {
15            ans[3] = '5';
16        }
17
18        if (ans[4] === '?') {
19            ans[4] = '9';
20        }
21
22        return ans.join('');
23    }
24}

C++ Solution

1class Solution {
2public:
3    string maximumTime(string time) {
4        string ans = time;
5
6        if (ans[0] == '?' || ans[1] == '?') {
7            if (ans[0] == '?') {
8                ans[0] = (ans[1] <= '3' || ans[1] == '?') ? '2' : '1';
9            }
10            if (ans[1] == '?') {
11                ans[1] = (ans[0] <= '1') ? '9' : '3';
12            }
13        }
14
15        if (ans[3] == '?') {
16            ans[3] = '5';
17        }
18
19        if (ans[4] == '?') {
20            ans[4] = '9';
21        }
22
23        return ans;
24    }
25};

C# Solution

1public class Solution {
2    public string MaximumTime(string time) {
3        char[] ans = time.ToCharArray();
4
5        if (ans[0] == '?' || ans[1] == '?') {
6            if (ans[0] == '?') {
7                ans[0] = (ans[1] <= '3' || ans[1] == '?') ? '2' : '1';
8            }
9            if (ans[1] == '?') {
10                ans[1] = (ans[0] <= '1') ? '9' : '3';
11            }
12        }
13
14        if (ans[3] == '?') {
15            ans[3] = '5';
16        }
17
18        if (ans[4] == '?') {
19            ans[4] = '9';
20        }
21
22        return new string(ans);
23    }
24}

Time and Space Complexity Analysis

The time complexity of all the solutions (Python, Java, JavaScript, C++, C#) is O(1) since the length of the input string is constant (5 characters).

The space complexity of all the solutions (Python, Java, JavaScript, C++, C#) is also O(1) since we don't use any additional space except for the result string which has a constant length (5 characters).