#2437

Easy

LeetCode Problem Workspace

Number of Valid Clock Times

Calculate how many valid digital clock times can be formed by replacing unknown digits in a string format hh:mm.

Problem Statement

You are given a string time of length 5 representing the current time in format hh:mm on a digital clock. Some digits are unknown and marked with a question mark '?'. Each '?' can be replaced with any digit from 0 to 9.

Return the total number of valid times that can be generated after replacing every '?' with a digit, ensuring hours are between 00 and 23 and minutes are between 00 and 59. For example, time = '?5:00' has 2 valid replacements.

Examples

Example 1

Input: time = "?5:00"

Output: 2

We can replace the ? with either a 0 or 1, producing "05:00" or "15:00". Note that we cannot replace it with a 2, since the time "25:00" is invalid. In total, we have two choices.

Example 2

Input: time = "0?:0?"

Output: 100

Each ? can be replaced by any digit from 0 to 9, so we have 100 total choices.

Example 3

Input: time = "??:??"

Output: 1440

There are 24 possible choices for the hours, and 60 possible choices for the minutes. In total, we have 24 * 60 = 1440 choices.

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.

Solution Approach

Brute Force Enumeration

Iterate over all possible digits for each '?', generate every combination, and count only those that form valid hh:mm times. This approach directly matches the string plus enumeration pattern and avoids missing edge cases like hours > 23.

Position-Based Multiplication

Compute the number of choices per position: the first hour digit can be 0-2, the second depends on the first, the minute digits can be 0-5 and 0-9. Multiply choices for each '?' to get total valid times. This optimizes enumeration without brute-force generation.

Validation Check

For each generated time string, check if hours <= 23 and minutes <= 59. Skip any invalid combinations. This ensures the count only includes valid clock times and directly addresses the problem's failure mode where naive replacement may exceed allowed ranges.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(1) in practice because there are at most 4 unknown digits and total combinations never exceed 24*60=1440. Space complexity is O(1) if counting, or O(1440) if storing all valid times.

What Interviewers Usually Probe

Do you recognize that each '?' position is independent within hour and minute limits?
Can you optimize counting instead of generating every time explicitly?
What are the boundary conditions for hours and minutes that could fail naive replacements?

Common Pitfalls or Variants

Common pitfalls

Replacing '?' without checking hour > 23 leads to invalid counts.
Ignoring that minute tens place must be 0-5 can overcount possibilities.
Multiplying choices blindly without considering dependency between first and second hour digits.

Follow-up variants

Count valid 12-hour clock times instead of 24-hour times.
Allow partial unknowns only in hours or only in minutes.
Return all valid time strings instead of just the count.

FAQ

How do I handle the '?' in the hours for 'Number of Valid Clock Times'?

Check constraints: if first hour digit is 2, second must be 0-3; otherwise 0-9. Multiply choices accordingly.

Can all '?' be replaced freely in minutes?

No, the tens place must be 0-5 while the units place can be 0-9 to stay within valid minute range.

Is brute-force generation feasible for this problem?

Yes, because at most 4 unknown digits result in 100-1440 combinations, manageable for enumeration.

How does string plus enumeration pattern apply here?

Each '?' represents a branching point; enumerating all digit options while checking validity fits this exact pattern.

What should I watch for to avoid miscounting?

Consider dependencies between hour digits, limits on minute digits, and skip any combinations exceeding hh:mm constraints.

terminal

Solution

Solution 1: Enumeration

We can directly enumerate all times from $00:00$ to $23:59$, then judge whether each time is valid, if so, increment the answer.

1

2

3

4

5

6

7

8

class Solution:
    def countTime(self, time: str) -> int:
        def check(s: str, t: str) -> bool:
            return all(a == b or b == '?' for a, b in zip(s, t))

        return sum(
            check(f'{h:02d}:{m:02d}', time) for h in range(24) for m in range(60)
        )

Solution 2: Optimized Enumeration

We can separately enumerate hours and minutes, count how many hours and minutes meet the condition, and then multiply them together.

1

2

3

4

5

6

7

8

class Solution:
    def countTime(self, time: str) -> int:
        def check(s: str, t: str) -> bool:
            return all(a == b or b == '?' for a, b in zip(s, t))

        return sum(
            check(f'{h:02d}:{m:02d}', time) for h in range(24) for m in range(60)
        )

Continue Practicing

#2468 split message based on limit #2309 greatest english letter in upper and lower case #2306 naming a company