algoadvance

Leetcode 2437. Number of Valid Clock Times

Problem Statement

You are given a string time in the form “HH:MM”, where some of the digits may be replaced by ‘?’. This string represents a time on a 24-hour clock (i.e., 00:00 to 23:59). Write a function to count the number of valid clock times possible by replacing each ‘?’ with a digit (0-9).

Clarifying Questions

1. Range of the String: Are we guaranteed that the input string is always in the format “HH:MM”?
   • Assumption: Yes, the string is always in the correct format.
2. Character Constraints: Are the positions of the ‘?’ fixed, and can they appear in any position?
   • Assumption: ‘?’ can appear in any of the positions, including multiple ones.
3. Valid Times: Should we consider leading zeros in valid times (e.g., 00:00 to 09:59)?
   • Assumption: Yes, leading zeros are valid in a 24-hour time format.

Strategy

To solve the problem, we’ll take the following approach:

1. Identify Positions of ‘?’: For each position in the “HH:MM” format, determine the valid digits that can replace ‘?’.
2. Count Valid Combinations: Multiply the number of valid choices for each position to get the total valid times.

Here’s a step-by-step breakdown for each position in the string “HH:MM”:

• For HH, the valid hour ranges are from 00 to 23.
  • The first digit (H1):
    • If it is ?, it can be 0, 1, or 2 depending on the second digit.
  • The second digit (H2):
    • If the first digit is 0 or 1, it can be 0 to 9.
    • If the first digit is 2, it can be 0 to 3.
• For MM, the valid minute ranges are from 00 to 59.
  • The first digit (M1):
    • If it is ?, it can be 0 to 5.
  • The second digit (M2):
    • If it is ?, it can be 0 to 9.

Code

Let’s implement this strategy in C++:

#include <iostream>
#include <string>
using namespace std;

int countTime(string time) {
    int count = 1;
    
    if (time[0] == '?') {
        if (time[1] == '?' || time[1] < '4') {
            count *= 3; // '0', '1', '2'
        } else {
            count *= 2; // '0', '1'
        }
    }
    
    if (time[1] == '?') {
        if (time[0] == '2') {
            count *= 4; // '0', '1', '2', '3'
        } else if (time[0] == '?') {
            count *= 10; // '0'-'9'
        } else {
            count *= 10; // '0'-'9'
        }
    }
    
    if (time[3] == '?') {
        count *= 6; // '0'-'5'
    }
    
    if (time[4] == '?') {
        count *= 10; // '0'-'9'
    }
    
    return count;
}

int main() {
    string time = "?4:5?";
    cout << countTime(time) << endl; // Example usage
    return 0;
}

Time Complexity

The time complexity of this solution is O(1) since it involves a constant number of operations regardless of the input size. The input size is always fixed at 5 characters.

Explanation

This code examines each position in the given time string and determines how many valid digits can replace the ‘?’ character:

• For HH, depending on the values of time[0] and time[1], different ranges of numbers are valid.
• For MM, the ranges are more straightforward and depend on the range of valid minutes.

Multiplying the number of choices for each position gives the total count of valid times.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?