Leetcode – Latest Time by Replacing Hidden Digits Solution

Spread the love

One of the problems you can solve on Leetcode is the “Latest Time by Replacing Hidden Digits” problem. It is an interesting problem that deals with string manipulation, conditional statements, and logic to find the maximum possible time in a 24-hour clock format by replacing hidden digits, represented by the character ‘?’.

Problem Statement

Before diving into the solution, let’s first understand the problem statement, which can be paraphrased as follows:

You are given a string time in the format “HH:MM,” where some of the digits can be hidden (represented by ‘?’). Your task is to replace the hidden digits to maximize the valid time in a 24-hour clock format.

Input

  • A string time of the format “HH:MM” where 0 <= H <= 23 and 0 <= M <= 59.

Output

  • Return the maximum valid time you can get by replacing the hidden digits.

Example

If the input time is “2?:?0”, then the maximum valid time you can get is “23:50”.

Brute-Force Approach

The simplest approach to solving this problem would be to generate all possible combinations by replacing ‘?’ with digits from 0 to 9 and validate each combination to find the maximum valid time. However, this approach is computationally expensive and unnecessary for this problem.

Optimized Approach

A more optimized solution would involve examining each position in the string and replacing ‘?’ with the maximum possible valid digit at that position.

Here is a Python code snippet to illustrate the approach:

def maximumTime(time):
    time_list = list(time)
    
    if time_list[0] == '?':
        time_list[0] = '2' if time_list[1] in ['?', '0', '1', '2', '3'] else '1'
        
    if time_list[1] == '?':
        time_list[1] = '3' if time_list[0] == '2' else '9'
        
    if time_list[3] == '?':
        time_list[3] = '5'
        
    if time_list[4] == '?':
        time_list[4] = '9'
        
    return ''.join(time_list)

Explanation:

  • First, we convert the time string into a list to easily manipulate individual characters.
  • Next, we check each position one by one:
    • For the first position (Hour’s tens place), the maximum possible digit is either 2 or 1, depending on the next digit. If the next digit is either 0, 1, 2, or 3, then the maximum possible digit for the first position can be 2; otherwise, it should be 1.
    • For the second position (Hour’s unit place), the maximum possible digit depends on the first position. If the first digit is 2, then the maximum possible digit for the second position is 3. Otherwise, it should be 9.
    • For the third position (Minute’s tens place), the maximum possible digit is 5.
    • For the fourth position (Minute’s unit place), the maximum possible digit is 9.
  • Finally, we join the list back into a string and return it.

Time and Space Complexity

The time complexity is O(1) because we are checking a fixed number of positions, and the space complexity is also O(1).

Testing the Function

Here are some test cases to validate the solution:

assert maximumTime("2?:?0") == "23:50"
assert maximumTime("0?:3?") == "09:39"
assert maximumTime("?4:??") == "14:59"
assert maximumTime("??:??") == "23:59"

Conclusion

The “Latest Time by Replacing Hidden Digits” problem on Leetcode provides a good exercise in string manipulation and logical reasoning. It is a relatively straightforward problem that can be solved efficiently with a time complexity of O(1). The key to solving this problem is to examine each position carefully and replace ‘?’ with the maximum possible valid digit.

Leave a Reply