Number of Valid Clock Times

Difficulty: Easy | Acceptance: 48.00% | Paid: No Topics: String, Enumeration

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 number of valid times you can get by replacing the hidden characters.

• Examples
• Constraints
• Brute Force
• Enumeration by Parts
• Mathematical Calculation

Examples

Input: time = "?5:00"
Output: 2
Explanation: We can replace the first ? with 0 or 1 to get valid times: "05:00" and "15:00".

Input: time = "0?:0?"
Output: 100
Explanation: We can replace the first ? with any digit from 0 to 9 and the second ? with any digit from 0 to 9, giving us 10 * 10 = 100 valid times.

Input: time = "??:??"
Output: 1440
Explanation: There are 24 * 60 = 1440 valid times.

Constraints

- time is a valid string of length 5 in the format "hh:mm".
- "00" <= hh <= "23"
- "00" <= mm <= "59"
- Some of the digits might be replaced with '?' and need to be replaced with digits from 0 to 9.

Brute Force

Intuition Since there are only 24 × 60 = 1440 possible valid times, we can iterate through all of them and count how many match the given pattern.

Steps

• Iterate through all hours from 0 to 23
• Iterate through all minutes from 0 to 59
• Format each time as “HH:MM”
• Check if it matches the input pattern (non-? characters must match)
• Count matching times

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

Complexity

• Time: O(1) - Fixed 1440 iterations
• Space: O(1)
• Notes: Simple but slightly less efficient than mathematical approach

Enumeration by Parts

Intuition Count valid hours and valid minutes separately, then multiply them since they are independent.

Steps

• Count hours from 0-23 that match the hour pattern
• Count minutes from 0-59 that match the minute pattern
• Return the product

class Solution:
    def countTime(self, time: str) -> int:
        hour_count = 0
        for h in range(24):
            h_str = f"{h:02d}"
            if (time[0] == '?' or time[0] == h_str[0]) and (time[1] == '?' or time[1] == h_str[1]):
                hour_count += 1
        
        minute_count = 0
        for m in range(60):
            m_str = f"{m:02d}"
            if (time[3] == '?' or time[3] == m_str[0]) and (time[4] == '?' or time[4] == m_str[1]):
                minute_count += 1
        
        return hour_count * minute_count

Complexity

• Time: O(1) - Fixed 84 iterations
• Space: O(1)
• Notes: More efficient than brute force by separating hour and minute checks

Mathematical Calculation

Intuition Directly compute the count using case analysis based on which positions are wildcards, leveraging the constraints of 24-hour time format.

Steps

• For hours: analyze cases based on whether first/second digit is ?
• For minutes: analyze cases based on whether first/second digit is ?
• Multiply the counts

class Solution:
    def countTime(self, time: str) -> int:
        h1, h2, m1, m2 = time[0], time[1], time[3], time[4]
        
        if h1 == '?' and h2 == '?':
            hour_count = 24
        elif h1 == '?':
            hour_count = 3 if h2 in '0123' else 2
        elif h2 == '?':
            if h1 == '0' or h1 == '1':
                hour_count = 10
            elif h1 == '2':
                hour_count = 4
            else:
                hour_count = 0
        else:
            hour_count = 1 if int(h1 + h2) < 24 else 0
        
        if m1 == '?' and m2 == '?':
            minute_count = 60
        elif m1 == '?':
            minute_count = 6
        elif m2 == '?':
            minute_count = 10 if m1 in '012345' else 0
        else:
            minute_count = 1 if int(m1 + m2) < 60 else 0
        
        return hour_count * minute_count

Complexity

• Time: O(1) - Constant time operations
• Space: O(1)
• Notes: Most efficient approach with no loops, but more verbose code