LeetCode 1736 - Latest Time by Replacing Hidden Digits

The problem presents a string time formatted as hh:mm, where h and m are digits representing hours and minutes, respectively. Some digits may be hidden and are represented by a question mark ?. The goal is to replace the ?

leetcodeeasystringgreedy

LeetCode Problem 1736

Difficulty: 🟢 Easy
Topics: String, Greedy

Solution

Problem Understanding

The problem presents a string time formatted as hh:mm, where h and m are digits representing hours and minutes, respectively. Some digits may be hidden and are represented by a question mark ?. The goal is to replace the ? characters with digits such that the resulting time is the latest valid time possible, considering the 24-hour format constraint (00:00 to 23:59).

The input guarantees that it is possible to construct a valid time by filling in the ? characters. Edge cases involve times where one or both digits of the hour or minute are unknown. For instance, ?4:5? and 2?:?0 require careful handling because replacing digits without considering constraints can lead to invalid hours or minutes. The output should preserve the original format hh:mm.

Constraints tell us that the input length is always 5, and the positions of : and digits are fixed. We do not need to handle malformed strings or completely invalid input.

Approaches

A brute-force approach would be to generate all possible valid times by replacing ? with digits 0 through 9, filter out invalid times, and then select the maximum. While correct, this approach is unnecessarily complex because it would require checking up to 10^4 combinations for every ? in the string, which is overkill given the simple constraints.

The key insight is that the latest valid time can be computed greedily, by determining the largest valid digit for each position in hh:mm while respecting the constraints of the 24-hour format. For example, if the first hour digit is 2, the second must be 0-3 to stay valid. If the first digit is 0 or 1, the second can be 0-9. Minutes are simpler because the first digit can be 0-5 and the second digit 0-9.

Approach Time Complexity Space Complexity Notes
Brute Force O(10^number_of_?) O(1) Try all digit combinations for ? and pick the largest valid time
Optimal O(1) O(1) Greedily replace ? with the largest valid digits based on constraints

Algorithm Walkthrough

  1. Start with the original time string.
  2. Examine the first digit of the hour (index 0). If it is ?, replace it with 2 if the second hour digit is unknown or less than 4; otherwise, replace with 1.
  3. Examine the second digit of the hour (index 1). If it is ?, replace it with 3 if the first hour digit is 2; otherwise, replace with 9.
  4. Examine the first digit of the minute (index 3). If it is ?, replace it with 5 because the maximum valid value is 59.
  5. Examine the second digit of the minute (index 4). If it is ?, replace it with 9.
  6. Return the resulting string after all replacements.

Why it works: The greedy choice at each position guarantees the maximum valid digit for that position without violating the 24-hour or minute constraints. Each digit is independent given the previous constraints, so the solution is guaranteed to be the latest possible time.

Python Solution

class Solution:
    def maximumTime(self, time: str) -> str:
        time_list = list(time)
        
        # Hour first digit
        if time_list[0] == '?':
            time_list[0] = '2' if time_list[1] == '?' or time_list[1] < '4' else '1'
        
        # Hour second digit
        if time_list[1] == '?':
            time_list[1] = '3' if time_list[0] == '2' else '9'
        
        # Minute first digit
        if time_list[3] == '?':
            time_list[3] = '5'
        
        # Minute second digit
        if time_list[4] == '?':
            time_list[4] = '9'
        
        return ''.join(time_list)

The Python solution converts the string into a list for mutable operations. It then replaces each ? based on the maximum allowable value that keeps the resulting time valid. Finally, it joins the list back into a string.

Go Solution

func maximumTime(time string) string {
    t := []byte(time)
    
    if t[0] == '?' {
        if t[1] == '?' || t[1] < '4' {
            t[0] = '2'
        } else {
            t[0] = '1'
        }
    }
    
    if t[1] == '?' {
        if t[0] == '2' {
            t[1] = '3'
        } else {
            t[1] = '9'
        }
    }
    
    if t[3] == '?' {
        t[3] = '5'
    }
    
    if t[4] == '?' {
        t[4] = '9'
    }
    
    return string(t)
}

The Go implementation follows the same logic as Python. A byte slice is used to allow in-place replacement. Indexing and character comparisons are straightforward in Go, and the final slice is converted back to a string.

Worked Examples

Example 1: time = "2?:?0"

Step Operation Result
Hour first digit ? → '2' 2?:?0
Hour second digit ? → '3' 23:?0
Minute first digit ? → '5' 23:50
Minute second digit already '0' 23:50

Example 2: time = "0?:3?"

Step Operation Result
Hour first digit '0' remains 0?:3?
Hour second digit ? → '9' 09:3?
Minute first digit '3' remains 09:3?
Minute second digit ? → '9' 09:39

Example 3: time = "1?:22"

Step Operation Result
Hour first digit '1' remains 1?:22
Hour second digit ? → '9' 19:22
Minute first digit '2' remains 19:22
Minute second digit '2' remains 19:22

Complexity Analysis

Measure Complexity Explanation
Time O(1) The string has fixed length 5, and we perform a constant number of operations
Space O(1) Only a mutable copy of the input string is created

The algorithm is constant time because the input length does not grow. No loops or recursion dependent on input size are used.

Test Cases

# Provided examples
assert Solution().maximumTime("2?:?0") == "23:50"  # Latest hour '23', latest minute '50'
assert Solution().maximumTime("0?:3?") == "09:39"  # Hour '09', minute '39'
assert Solution().maximumTime("1?:22") == "19:22"  # Hour '19', minute '22'

# Boundary cases
assert Solution().maximumTime("??:??") == "23:59"  # All unknown, maximum time
assert Solution().maximumTime("?4:5?") == "14:59"  # First hour '?' constrained by second digit '4'
assert Solution().maximumTime("2?:??") == "23:59"  # First hour '2', all remaining maxed
assert Solution().maximumTime("0?:0?") == "09:09"  # Single-digit constraints on hour and minute
Test Why
"2?:?0" Tests hour first digit '2' and minute second fixed
"0?:3?" Tests hour first digit '0' and minute unknowns
"1?:22" Tests hour first digit '1' with known minute
"??:??" All unknown, should produce maximum time
"?4:5?" First hour constrained by second hour digit
"2?:??" First hour '2' with all unknowns
"0?:0?" Tests handling of multiple unknowns in first digits

Edge Cases

Case 1: All digits unknown ("??:??"): This tests whether the algorithm correctly maximizes each component independently. The algorithm should fill '2' for the first hour, '3' for the second, '5' for the first minute, and '9' for the second minute.

Case 2: First hour digit '?' but second digit > 3 ("?4:??"): This is tricky because the first hour digit cannot be '2' (24 is invalid). The algorithm correctly chooses '1' to ensure the hour remains valid.

Case 3: Minute digits unknown ("hh:??"): Ensures that unknown minutes are always replaced with the maximum valid value. The first minute digit cannot exceed '5',