#3114

Easy

LeetCode Problem Workspace

Latest Time You Can Obtain After Replacing Characters

Given a time string with "?" characters, replace them to form the latest valid 12-hour time.

Problem Statement

You are given a string s representing a 12-hour format time where some of the digits are replaced with "?". The string is in the form of "HH:MM", where HH is between 00 and 11, and MM is between 00 and 59. You must replace the "?" characters to form the latest valid 12-hour time.

The goal is to replace the '?' characters in such a way that the resulting time is the largest possible valid 12-hour time. The resulting time must also adhere to the format "HH:MM", with hours between 00 and 11 and minutes between 00 and 59. You must also make sure that the time is valid after replacing the '?' characters.

Examples

Example 1

Input: s = "1?:?4"

Output: "11:54"

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

Example 2

Input: s = "0?:5?"

Output: "09:59"

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.

Solution Approach

Brute Force Search

One approach is to generate all possible replacements for the '?' characters and check each one to see if it forms a valid 12-hour time. This is a straightforward brute force approach where all possible combinations are checked, but it can be inefficient for larger cases.

Greedy Approach

Another more efficient approach is to greedily replace '?' starting with the highest possible digits for hours and minutes, while ensuring the time remains valid. For example, for the first '?' in the hour part, replace it with 1 if possible, otherwise replace it with 0.

Validation Function

After replacing all '?' characters, we must validate that the resulting string forms a valid 12-hour time. This can be done by checking if the hour is between 00 and 11, and the minute is between 00 and 59.

Complexity Analysis

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

The time and space complexity depend on the chosen approach. A brute force approach would have a higher time complexity, while the greedy approach has a more optimized time complexity by minimizing the number of checks needed.

What Interviewers Usually Probe

Look for an understanding of string manipulation.
The interviewer may focus on efficiency or correctness of validation.
The problem may signal an interest in optimization strategies, like greedy algorithms.

Common Pitfalls or Variants

Common pitfalls

Failing to check the bounds of valid hours and minutes when replacing '?' characters.
Choosing incorrect digits when replacing '?' characters, leading to invalid times.
Overcomplicating the problem by trying overly complex solutions when a greedy approach is sufficient.

Follow-up variants

Change the range of hours (e.g., 00-23) to test different time formats.
Introduce more '?' characters to increase the complexity.
Modify the problem to generate the earliest valid time instead of the latest.

FAQ

What is the time format for this problem?

The time is represented in the 12-hour format 'HH:MM', where hours range from 00 to 11 and minutes range from 00 to 59.

How do I validate if the time after replacement is correct?

You need to ensure that the hour is between 00 and 11, and the minute is between 00 and 59. Any other value is invalid.

What is the goal of the problem?

The goal is to replace '?' characters with digits such that the resulting time is the latest valid 12-hour time possible.

Can I use a brute force solution for this problem?

Yes, but it may not be efficient. A brute force approach checks all possible combinations, whereas a greedy approach is more optimized.

How does GhostInterview help with solving this problem?

GhostInterview provides step-by-step guidance and suggestions to help you choose the best approach, debug edge cases, and validate your solution.

terminal

Solution

Solution 1: Enumeration

We can enumerate all times from large to small, where the hour $h$ ranges from $11$ to $0$, and the minute $m$ ranges from $59$ to $0$. For each time $t$, we check whether each digit of $t$ matches the corresponding digit in $s$ (if the corresponding digit in $s$ is not "?"). If it does, then we have found the answer and return $t$.

1

2

3

4

5

6

7

class Solution:
    def findLatestTime(self, s: str) -> str:
        for h in range(11, -1, -1):
            for m in range(59, -1, -1):
                t = f"{h:02d}:{m:02d}"
                if all(a == b for a, b in zip(s, t) if a != "?"):
                    return t

Solution 2: Judge Each Digit

We can judge each digit of $s$ one by one. If it is "?", we determine the value of this digit based on the characters before and after it. Specifically, we have the following rules:

1

2

3

4

5

6

7

class Solution:
    def findLatestTime(self, s: str) -> str:
        for h in range(11, -1, -1):
            for m in range(59, -1, -1):
                t = f"{h:02d}:{m:02d}"
                if all(a == b for a, b in zip(s, t) if a != "?"):
                    return t

Continue Practicing

#3234 count the number of substrings with dominant ones #2947 count beautiful substrings i #2844 minimum operations to make a special number