Latest Time You Can Obtain After Replacing Characters

Easy

Asked by:

18 views

Topics:

StringsGreedy Algorithms

You are given a string s representing a 12-hour format time where some of the digits (possibly none) are replaced with a "?".

12-hour times are formatted as "HH:MM", where HH is between 00 and 11, and MM is between 00 and 59. The earliest 12-hour time is 00:00, and the latest is 11:59.

You have to replace all the "?" characters in s with digits such that the time we obtain by the resulting string is a valid 12-hour format time and is the latest possible.

Return the resulting string.

Example 1:

Input: s = "1?:?4"

Output: "11:54"

Explanation: The latest 12-hour format time we can achieve by replacing "?" characters is "11:54".

Example 2:

Input: s = "0?:5?"

Output: "09:59"

Explanation: The latest 12-hour format time we can achieve by replacing "?" characters is "09:59".

Constraints:

s.length == 5
s[2] is equal to the character ":".
All characters except s[2] are digits or "?" characters.
The input is generated such that there is at least one time between "00:00" and "11:59" that you can obtain after replacing the "?" characters.

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 are the possible characters in the input string 'time', and what characters are allowed to replace the '?' characters with?
Are there any constraints on the 'time' string's format, such as length or specific positions of the '?' characters?
If there are multiple valid 'latest' times, should I return any one of them, or is there a specific rule to determine which one to return?
What should I return if it's impossible to construct a valid time (e.g., if the input is '??:??' and the replacements lead to an invalid time like '24:00')?
Can the input 'time' string ever be null or empty?

Brute Force Solution

Approach

The brute force approach for this question means we try every possible combination of replacing the question marks in the input string. We then validate each resulting time to see if it is valid, keeping track of the latest valid time we find. It's like trying every single possibility until we find the best one that fits the rules.

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

Consider the input time string, which contains question marks that can be replaced with digits.
Start by replacing each question mark with every possible digit, one combination at a time.
For example, if the first character is a question mark, try replacing it with 0, then 1, then 2, all the way up to 9. Then, move to the next question mark and repeat the process.
After replacing all the question marks with digits, we will have a complete time string.
Check if the generated time is a valid time according to the 24-hour clock format (hours between 00 and 23, minutes between 00 and 59).
If the generated time is valid, compare it with the latest valid time found so far. If it is later, update the latest valid time.
Repeat steps 2 through 6 for all possible combinations of digits replacing the question marks.
After trying all combinations, the latest valid time found is the answer.

Code Implementation

def latest_time_brute_force(time_string):
    latest_valid_time = ""

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

    def generate_times(index, current_time):
        nonlocal latest_valid_time

        if index == len(time_string):
            hour = int(current_time[0:2])
            minute = int(current_time[3:5])

            # Validate time after generating full combination
            if is_valid_time(hour, minute):
                if latest_valid_time == "" or current_time > latest_valid_time:
                    latest_valid_time = current_time
            return

        if time_string[index] == '?':
            # Try every possible digit from 0 to 9
            for digit in range(10):
                new_time = current_time[:index] + str(digit) + current_time[index+1:]
                generate_times(index + 1, new_time)
        else:
            generate_times(index + 1, current_time)

    generate_times(0, time_string)
    return latest_valid_time

Big(O) Analysis

Time Complexity

O(10^k) – Let k be the number of question marks in the input string. For each question mark, we iterate through 10 possible digits (0-9). Since we have to explore every possible combination of digits for each question mark, the time complexity grows exponentially with the number of question marks. Validating the time string takes constant time O(1). Therefore, the overall time complexity is O(10^k), where k is the number of question marks in the input string. The input size n is constant (length of time string = 5) and doesn't directly affect the complexity, making 10^k the dominant factor.

Space Complexity

O(N) – The brute force approach explores all possible combinations of replacing question marks. This can be implemented using recursion or iteration with a temporary string to store the intermediate time string being generated at each step. The maximum depth of recursion or the size of the temporary string will be proportional to the length of the input time string, which is a constant 5 characters (HH:MM). Thus, it creates N time strings where N is the length of the input. Therefore, the space complexity scales linearly with the input size.

Optimal Solution

Approach

The goal is to maximize the time we can create by filling in question marks. We should prioritize placing the largest possible digits in each position, while respecting the constraints of what a valid time looks like.

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

Start by looking at the first digit of the hour.
If it's a question mark, decide what it should be. If the second digit of the hour is also a question mark, then the first digit can be '2'. Otherwise, it can only be '1' or '0'. We want to make it '2' if possible, to get the highest hour.
Now look at the second digit of the hour. If it's a question mark, decide what it should be. If the first digit is '2', then this one can be at most '3'. Otherwise, if the first digit is '0' or '1', this one can be as big as '9'.
Move to the first digit of the minute. If it's a question mark, make it '5', since that's the largest possible value for that position.
Finally, look at the second digit of the minute. If it's a question mark, make it '9', since that's the largest possible value.
Combine all the digits to get the latest possible valid time.

Code Implementation

def latest_time_from_string(time): 
    time_characters = list(time)

    # Determine the first digit of the hour
    if time_characters[0] == '?':
        if time_characters[1] == '?':
            time_characters[0] = '2'
        elif int(time_characters[1]) <= 3:
            time_characters[0] = '2'
        else:
            time_characters[0] = '1'

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

    # The third character must be a colon.  No logic needed.

    # Prioritize '5' to maximize the minute.
    if time_characters[3] == '?':
        time_characters[3] = '5'

    # Prioritize '9' to maximize the seconds.
    if time_characters[4] == '?':
        time_characters[4] = '9'

    return "".join(time_characters)

Big(O) Analysis

Time Complexity

O(1) – The algorithm examines at most four characters in a string, each character representing a digit in the time (HH:MM). The operations performed on these characters involve a fixed number of comparisons and assignments to determine the largest possible digit. Since the number of operations is constant regardless of the input time, the time complexity is O(1).

Space Complexity

O(1) – The provided solution operates directly on the input string, modifying it in place. It uses a fixed number of variables to store intermediate values like the determined digits. No auxiliary data structures that scale with the input string's length (N, which is always 5 for a time string) are created. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty time string	Return null or an appropriate error message, as an empty input is invalid.
Time string contains invalid characters besides '?'	Validate the input string and return an error if invalid characters are found, ensuring correct processing.
Time string of incorrect length	Check if the length of the input string is exactly 5 and return an error if it isn't, enforcing the expected format.
All characters in the time string are '?'	Replace all '?' characters to form the latest possible time, i.e., 23:59.
First digit is '?' and second digit is not, but forces first digit to be '1'	Handle the constraint where if the second digit is greater than '3', the first digit must be '1'.
Second digit is '?' and first digit is '2'	If the first digit is '2', replace '?' with '3' if it's the second digit of the hour, else use 5 or 9 if it's minutes or seconds place, respectively.
Input that forms an invalid time after replacing question marks	Ensure the generated time is valid after replacement, which should be inherently guaranteed if each '?' is replaced based on its position and preceding chars.
Integer overflow if calculations are not handled carefully	This is not applicable because we are dealing with string manipulation and direct character replacement and no integer overflow is anticipated.

Null or empty time string

How to Handle:

Return null or an appropriate error message, as an empty input is invalid.

Time string contains invalid characters besides '?'

How to Handle:

Validate the input string and return an error if invalid characters are found, ensuring correct processing.

Time string of incorrect length

How to Handle:

Check if the length of the input string is exactly 5 and return an error if it isn't, enforcing the expected format.

All characters in the time string are '?'

How to Handle:

Replace all '?' characters to form the latest possible time, i.e., 23:59.

First digit is '?' and second digit is not, but forces first digit to be '1'

How to Handle:

Handle the constraint where if the second digit is greater than '3', the first digit must be '1'.

Second digit is '?' and first digit is '2'

How to Handle:

If the first digit is '2', replace '?' with '3' if it's the second digit of the hour, else use 5 or 9 if it's minutes or seconds place, respectively.

Input that forms an invalid time after replacing question marks

How to Handle:

Ensure the generated time is valid after replacement, which should be inherently guaranteed if each '?' is replaced based on its position and preceding chars.

Integer overflow if calculations are not handled carefully

How to Handle:

This is not applicable because we are dealing with string manipulation and direct character replacement and no integer overflow is anticipated.