Jobs

Interviews

Discussions

Latest Time by Replacing Hidden Digits

Easy

Asked by:

8 views

Topics:

Strings

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 from time by replacing the hidden digits.

Example 1:

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

Example 2:

Input: time = "0?:3?"
Output: "09:39"

Example 3:

Input: time = "1?:22"
Output: "19:22"

Constraints:

time is in the format hh:mm.
It is guaranteed that you can produce a valid time from the given string.

Try coding it in LeetCode

Latest Time by Replacing Hidden Digits

Easy

Asked by:

8 views

Topics:

Strings

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 from time by replacing the hidden digits.

Example 1:

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

Example 2:

Input: time = "0?:3?"
Output: "09:39"

Example 3:

Input: time = "1?:22"
Output: "19:22"

Constraints:

time is in the format hh:mm.
It is guaranteed that you can produce a valid time from the given string.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters besides '?' will be in the input string, and what is the expected length of the input string?
If there are multiple valid times, should I return the earliest, latest, or any valid time?
If no valid time can be formed, what should I return (e.g., null, an empty string, or an error message)?
Are the question marks independent, or does filling one affect the valid options for another (i.e., is it purely based on the local constraints)?
Can I assume the input string will always have the format 'HH:MM', or should I handle cases with incorrect formatting?

Brute Force Solution

Approach

The goal is to find the latest possible time by filling in question marks with digits. Brute force means we will try out every possible digit for each question mark. We then check if each resulting time is valid and pick the latest one.

Here's how the algorithm would work step-by-step:

Consider the first question mark. Try replacing it with every possible digit (0 through 9).
For each of those possibilities, move to the next question mark and again try replacing it with every possible digit.
Keep doing this for every question mark in the time string. You will end up with many different combinations of digits.
For each complete time combination, check if it's a valid time. For example, the hour must be between 00 and 23, and the minute must be between 00 and 59.
If the time is valid, compare it to the latest valid time you've found so far. If the current time is later, then it becomes the new latest valid time.
After trying every single combination of digits, the latest valid time you have is the answer.

Code Implementation

def latest_time_by_replacing_hidden_digits_brute_force(time):
    latest_valid_time = ""

    def is_valid_time(hour, minute):
        return 0 <= hour <= 23 and 0 <= minute <= 59

    def generate_times(index, current_time):
        nonlocal latest_valid_time
        if index == 5:
            hour = int(current_time[0:2])
            minute = int(current_time[3:5])
            # Check if the generated time is valid.
            if is_valid_time(hour, minute):
                if latest_valid_time == "" or current_time > latest_valid_time:
                    latest_valid_time = current_time
            return

        if time[index] == '?':
            for digit in range(10):
                new_time = list(current_time)
                new_time[index] = str(digit)
                generate_times(index + 1, "".join(new_time))
        else:
            generate_times(index + 1, current_time)

    # Handle the colon character without processing it as a digit
    generate_times(0, list(time))

    return latest_valid_time

Big(O) Analysis

Time Complexity

O(1) – The input string 'time' has a fixed size of 5 (HH:MM). The algorithm iterates through each question mark, replacing it with digits from 0-9. Since the number of question marks is limited by the fixed size of the string, the number of possible time combinations is bounded by a constant (at most 10^4 if all digits are question marks). Therefore, the number of operations does not depend on the size of the input in a way that grows indefinitely, and the time complexity is O(1).

Space Complexity

O(1) – The described brute force approach explores all possible digit combinations by repeatedly trying each digit from 0-9 at each question mark position. Although it iterates through possibilities, it does not explicitly create or store a collection of intermediate time strings. The space used is dominated by a few constant-sized variables to store the current best valid time and potentially temporary variables used to modify the input string, resulting in constant auxiliary space, irrespective of the input time string's length (N).

Optimal Solution

Approach

The goal is to find the latest possible time given a string with hidden digits. Instead of trying all combinations, we'll strategically fill in the blanks to maximize each digit from left to right, ensuring the resulting time is always valid.

Here's how the algorithm would work step-by-step:

Start by looking at the first digit of the hour. If it's hidden, we want to make it as big as possible, but not so big that the overall time is invalid. So, if the second digit of the hour is less than 4, the first digit should be '2'. Otherwise, it should be '1'.
Next, look at the second digit of the hour. If it's hidden and the first digit is '2', then the biggest it can be is '3'. If the first digit is something else (like '0' or '1'), the second digit can be '9'.
Now, move to the first digit of the minutes. If it's hidden, we always want it to be '5' because that's the biggest it can be.
Finally, look at the second digit of the minutes. If it's hidden, we always want it to be '9' because that's the biggest it can be.
By filling in the hidden digits from left to right with the largest possible valid values, we ensure we get the latest valid time.

Code Implementation

def latest_time_by_replacing_hidden_digits(time):
    time_list = list(time)

    # Determine the first digit of the hour.
    if time_list[0] == '?':
        if time_list[1] == '?' or int(time_list[1]) < 4:
            time_list[0] = '2'
        else:
            time_list[0] = '1'

    # Determine the second digit of the hour.
    if time_list[1] == '?':
        if time_list[0] == '2':
            time_list[1] = '3'
        else:
            time_list[1] = '9'

    # The largest valid value for minutes first digit is 5.
    if time_list[3] == '?':
        time_list[3] = '5'

    # Always maximize the second digit of the minutes.
    if time_list[4] == '?':
        time_list[4] = '9'

    return "".join(time_list)

Big(O) Analysis

Time Complexity

O(1) – The algorithm inspects a fixed number of characters in the input string (always 4 representing the time HH:MM). The number of operations performed is independent of the size of the input. Therefore, the time complexity is constant, represented as O(1).

Space Complexity

O(1) – The algorithm modifies the input string in-place and uses only a few constant space variables to store the intermediate results while filling the missing digits. No auxiliary data structures like arrays, lists, or hashmaps are used that scale with the input size. Therefore, the auxiliary space complexity is constant, independent of the input string length, which is a fixed size (5 characters).

Edge Cases

Case	How to Handle
Input string is null or empty	Return an appropriate error message or a default value like '00:00' based on problem constraints, after validating input.
Input string length is not 5 or format is incorrect (not 'HH:MM')	Validate the length and format of the input and return an error if incorrect.
All digits are hidden ('??:??')	The algorithm should correctly generate the maximum possible time '23:59' through its iterative replacement process.
Hour is partially defined (e.g., '?3:??')	The algorithm needs to intelligently fill the unknown hour digit, considering the existing one (in this case, the first digit must be either '0', '1', or '2').
Minute is partially defined (e.g., '??:?9')	The algorithm should choose the maximum possible digit for the undefined part of the minute, respecting the constraints (in this case the first digit must be between '0' and '5').
Input like '24:00' or '1?:??'	The algorithm should intelligently backtrack and try other valid numbers, such as changing the first question mark to '1' to make it '19:59' instead of failing.
Hour allows two values (e.g., '?3:??', becomes 23:??). Minutes become invalid (e.g. 23:6?).	Backtracking or constraints propogation is necessary to ensure a valid minute construction if hour selection initially leads to minute overbound.
No valid time can be constructed due to conflicting constraints.	The algorithm should return a specific error value or a default invalid time indication like 'invalid' or 'error'.

Input string is null or empty

How to Handle:

Return an appropriate error message or a default value like '00:00' based on problem constraints, after validating input.

Input string length is not 5 or format is incorrect (not 'HH:MM')

How to Handle:

Validate the length and format of the input and return an error if incorrect.

All digits are hidden ('??:??')

How to Handle:

The algorithm should correctly generate the maximum possible time '23:59' through its iterative replacement process.

Hour is partially defined (e.g., '?3:??')

How to Handle:

The algorithm needs to intelligently fill the unknown hour digit, considering the existing one (in this case, the first digit must be either '0', '1', or '2').

Minute is partially defined (e.g., '??:?9')

How to Handle:

The algorithm should choose the maximum possible digit for the undefined part of the minute, respecting the constraints (in this case the first digit must be between '0' and '5').

Input like '24:00' or '1?:??'

How to Handle:

The algorithm should intelligently backtrack and try other valid numbers, such as changing the first question mark to '1' to make it '19:59' instead of failing.

Hour allows two values (e.g., '?3:??', becomes 23:??). Minutes become invalid (e.g. 23:6?).

How to Handle:

Backtracking or constraints propogation is necessary to ensure a valid minute construction if hour selection initially leads to minute overbound.

No valid time can be constructed due to conflicting constraints.

How to Handle:

The algorithm should return a specific error value or a default invalid time indication like 'invalid' or 'error'.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters besides '?' will be in the input string, and what is the expected length of the input string?
If there are multiple valid times, should I return the earliest, latest, or any valid time?
If no valid time can be formed, what should I return (e.g., null, an empty string, or an error message)?
Are the question marks independent, or does filling one affect the valid options for another (i.e., is it purely based on the local constraints)?
Can I assume the input string will always have the format 'HH:MM', or should I handle cases with incorrect formatting?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider the first question mark. Try replacing it with every possible digit (0 through 9).
For each of those possibilities, move to the next question mark and again try replacing it with every possible digit.
Keep doing this for every question mark in the time string. You will end up with many different combinations of digits.
For each complete time combination, check if it's a valid time. For example, the hour must be between 00 and 23, and the minute must be between 00 and 59.
If the time is valid, compare it to the latest valid time you've found so far. If the current time is later, then it becomes the new latest valid time.
After trying every single combination of digits, the latest valid time you have is the answer.

Code Implementation

def latest_time_by_replacing_hidden_digits_brute_force(time):
    latest_valid_time = ""

    def is_valid_time(hour, minute):
        return 0 <= hour <= 23 and 0 <= minute <= 59

    def generate_times(index, current_time):
        nonlocal latest_valid_time
        if index == 5:
            hour = int(current_time[0:2])
            minute = int(current_time[3:5])
            # Check if the generated time is valid.
            if is_valid_time(hour, minute):
                if latest_valid_time == "" or current_time > latest_valid_time:
                    latest_valid_time = current_time
            return

        if time[index] == '?':
            for digit in range(10):
                new_time = list(current_time)
                new_time[index] = str(digit)
                generate_times(index + 1, "".join(new_time))
        else:
            generate_times(index + 1, current_time)

    # Handle the colon character without processing it as a digit
    generate_times(0, list(time))

    return latest_valid_time

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the first digit of the hour. If it's hidden, we want to make it as big as possible, but not so big that the overall time is invalid. So, if the second digit of the hour is less than 4, the first digit should be '2'. Otherwise, it should be '1'.
Next, look at the second digit of the hour. If it's hidden and the first digit is '2', then the biggest it can be is '3'. If the first digit is something else (like '0' or '1'), the second digit can be '9'.
Now, move to the first digit of the minutes. If it's hidden, we always want it to be '5' because that's the biggest it can be.
Finally, look at the second digit of the minutes. If it's hidden, we always want it to be '9' because that's the biggest it can be.
By filling in the hidden digits from left to right with the largest possible valid values, we ensure we get the latest valid time.

Code Implementation

def latest_time_by_replacing_hidden_digits(time):
    time_list = list(time)

    # Determine the first digit of the hour.
    if time_list[0] == '?':
        if time_list[1] == '?' or int(time_list[1]) < 4:
            time_list[0] = '2'
        else:
            time_list[0] = '1'

    # Determine the second digit of the hour.
    if time_list[1] == '?':
        if time_list[0] == '2':
            time_list[1] = '3'
        else:
            time_list[1] = '9'

    # The largest valid value for minutes first digit is 5.
    if time_list[3] == '?':
        time_list[3] = '5'

    # Always maximize the second digit of the minutes.
    if time_list[4] == '?':
        time_list[4] = '9'

    return "".join(time_list)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input string is null or empty	Return an appropriate error message or a default value like '00:00' based on problem constraints, after validating input.
Input string length is not 5 or format is incorrect (not 'HH:MM')	Validate the length and format of the input and return an error if incorrect.
All digits are hidden ('??:??')	The algorithm should correctly generate the maximum possible time '23:59' through its iterative replacement process.
Hour is partially defined (e.g., '?3:??')	The algorithm needs to intelligently fill the unknown hour digit, considering the existing one (in this case, the first digit must be either '0', '1', or '2').
Minute is partially defined (e.g., '??:?9')	The algorithm should choose the maximum possible digit for the undefined part of the minute, respecting the constraints (in this case the first digit must be between '0' and '5').
Input like '24:00' or '1?:??'	The algorithm should intelligently backtrack and try other valid numbers, such as changing the first question mark to '1' to make it '19:59' instead of failing.
Hour allows two values (e.g., '?3:??', becomes 23:??). Minutes become invalid (e.g. 23:6?).	Backtracking or constraints propogation is necessary to ensure a valid minute construction if hour selection initially leads to minute overbound.
No valid time can be constructed due to conflicting constraints.	The algorithm should return a specific error value or a default invalid time indication like 'invalid' or 'error'.

Input string is null or empty

How to Handle:

Return an appropriate error message or a default value like '00:00' based on problem constraints, after validating input.

Input string length is not 5 or format is incorrect (not 'HH:MM')

How to Handle:

Validate the length and format of the input and return an error if incorrect.

All digits are hidden ('??:??')

How to Handle:

The algorithm should correctly generate the maximum possible time '23:59' through its iterative replacement process.

Hour is partially defined (e.g., '?3:??')

How to Handle:

The algorithm needs to intelligently fill the unknown hour digit, considering the existing one (in this case, the first digit must be either '0', '1', or '2').

Minute is partially defined (e.g., '??:?9')

How to Handle:

The algorithm should choose the maximum possible digit for the undefined part of the minute, respecting the constraints (in this case the first digit must be between '0' and '5').

Input like '24:00' or '1?:??'

How to Handle:

The algorithm should intelligently backtrack and try other valid numbers, such as changing the first question mark to '1' to make it '19:59' instead of failing.

Hour allows two values (e.g., '?3:??', becomes 23:??). Minutes become invalid (e.g. 23:6?).

How to Handle:

Backtracking or constraints propogation is necessary to ensure a valid minute construction if hour selection initially leads to minute overbound.

No valid time can be constructed due to conflicting constraints.

How to Handle:

The algorithm should return a specific error value or a default invalid time indication like 'invalid' or 'error'.