algoadvance

You are given a time in the format of HH:MM, where some of the digits are hidden (represented by ?). The task is to replace the hidden digits in such a way that the resulting time is the latest possible valid time. The given string will always satisfy the format HH:MM.

Example

Example 1:

• Input: "?4:5?"
• Output: "14:59"

Example 2:

• Input: "23:5?"
• Output: "23:59"

Example 3:

• Input: "2?:22"
• Output: "23:22"

Clarifying Questions:

1. Will the input always be in the format HH:MM with exactly two characters for hours and two for minutes?
   • Yes, the format is guaranteed.
2. Can we assume the input string will only contain valid placeholder characters for unknown digits?
   • Yes, only ? characters will be used as placeholders.

Strategy:

To solve this problem, we need to consider how to replace each ? to create the maximum possible time:

1. Hours place (HH):
   • First digit: If the first digit is ?, it can be either 2 if the second digit is 0-3, or 1 if the second digit is 4-9.
   • Second digit: If the second digit is ?, it can be 9 if the first digit is 0 or 1, or 3 if the first digit is 2.
2. Minutes place (MM):
   • Always replace ? with the highest possible valid digit (9).

Code Implementations:

def maximumTime(time: str) -> str:
    hours, minutes = time.split(":")
    
    # Handle hours
    if hours[0] == "?":
        if hours[1] == "?" or int(hours[1]) <= 3:
            hours = "2" + hours[1]
        else:
            hours = "1" + hours[1]
    if hours[1] == "?":
        if hours[0] == "2":
            hours = hours[0] + "3"
        else:
            hours = hours[0] + "9"
    
    # Handle minutes
    if minutes[0] == "?":
        minutes = "5" + minutes[1]
    if minutes[1] == "?":
        minutes = minutes[0] + "9"
    
    return f"{hours}:{minutes}"

# Example usage
print(maximumTime("?4:5?"))  # Should return "14:59"
print(maximumTime("23:5?"))  # Should return "23:59"
print(maximumTime("2?:22"))  # Should return "23:22"

Time Complexity:

• O(1): The solution involves a fixed number of operations regardless of the input content or size.

This code efficiently finds and replaces the ? characters, ensuring the resulting time is the latest possible valid time.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?