What is the time complexity of the Greedy Approach?

The Greedy Approach has O(1) time complexity as we process a fixed number of characters.

What is the space complexity of the Greedy Approach?

The Greedy Approach has O(1) space complexity as we use a fixed amount of extra space.

What is the time complexity of the Brute Force Approach?

The Brute Force Approach has O(1) time complexity as we iterate through all 1440 possible times.

What is the space complexity of the Brute Force Approach?

The Brute Force Approach has O(1) space complexity for storing the result.

Latest Time by Replacing Hidden Digits

Difficulty: Easy | Acceptance: 43.80% | Paid: No Topics: String, Greedy

You are given a string time in the form of hh:mm, where some of the digits in the string are hidden (represented by ?).

The valid times are those inclusively between 00:00 and 23:59.

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

Examples
Constraints
Greedy Approach
Brute Force Approach

Examples

Input: time = "2?:?0"
Output: "23:50"
Explanation: The latest hour beginning with 2 is 23. The latest minute ending with 0 is 50.

Input: time = "0?:??"
Output: "09:59"
Explanation: The latest hour beginning with 0 is 09. The latest minute is 59.

Input: time = "1?:22"
Output: "19:22"
Explanation: The latest hour beginning with 1 is 19. The minute is fixed as 22.

Constraints

time is in the format hh:mm
time.length == 5
Some digits may be '?'

Greedy Approach

Intuition For each position with a ’?’, we greedily choose the maximum valid digit based on the constraints of the time format and the values of other positions.

Steps

For position 0 (hours tens): If position 1 is ’?’ or 0-3, use ‘2’. If position 1 is 4-9, use ‘1’. If position 0 is not ’?’, keep it.
For position 1 (hours units): If position 0 is ‘2’, use ‘3’. Otherwise, use ‘9’. If position 1 is not ’?’, keep it.
For position 3 (minutes tens): Use ‘5’. If position 3 is not ’?’, keep it.
For position 4 (minutes units): Use ‘9’. If position 4 is not ’?’, keep it.

python

class Solution:
    def maximumTime(self, time: str) -> str:
        time = list(time)
        
        # Handle position 0 (hours tens)
        if time[0] == '?':
            if time[1] == '?' or int(time[1]) &lt;= 3:
                time[0] = '2'
            else:
                time[0] = '1'
        
        # Handle position 1 (hours units)
        if time[1] == '?':
            if time[0] == '2':
                time[1] = '3'
            else:
                time[1] = '9'
        
        # Handle position 3 (minutes tens)
        if time[3] == '?':
            time[3] = '5'
        
        # Handle position 4 (minutes units)
        if time[4] == '?':
            time[4] = '9'
        
        return ''.join(time)

Complexity

Time: O(1) - We process a fixed number of characters
Space: O(1) - We use a fixed amount of extra space
Notes: This is the optimal approach with constant time and space complexity.

Brute Force Approach

Intuition Try all possible combinations of digits for ’?’ positions and find the maximum valid time.

Steps

Generate all possible combinations by replacing ’?’ with valid digits
Check if each combination is a valid time
Keep track of the maximum valid time found

python

class Solution:
    def maximumTime(self, time: str) -> str:
        max_time = ""
        
        for h in range(24):
            for m in range(60):
                candidate = f"{h:02d}:{m:02d}"
                valid = True
                
                for i in range(5):
                    if time[i] != '?' and time[i] != candidate[i]:
                        valid = False
                        break
                
                if valid:
                    max_time = candidate
        
        return max_time

Complexity

Time: O(24 × 60 × 5) = O(1) - Constant time since we iterate through all possible times
Space: O(1) - Constant space for storing the result
Notes: While this is also O(1), it’s less efficient than the greedy approach as it checks all 1440 possible times.