3114. Latest Time You Can Obtain After Replacing Characters

EasyStringEnumeration

Problem Description

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.

Your task is 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.

Intuition

To solve this problem, the strategy is to consider all possible times and choose the latest valid time that matches the pattern given by s. We begin by enumerating all possible hours HH in descending order from 11 to 0. For each hour, we then enumerate all possible minutes MM in descending order from 59 to 0. This way, we first check the latest possible times.

For every time t constructed as HH:MM, we compare it with the input string s. If there's a match for each part of the string where s has a specific digit (ignoring the "?"), then this is the valid time we are looking for. We return this time immediately since we are iterating from the largest possible values to the smallest, ensuring that the first valid time found is the latest one.

Solution Approach

Enumeration

The solution involves enumerating and checking all possible times, beginning with the largest and moving to the smallest. This ensures that the first valid time we find is indeed the latest possible valid time.

Loop Through Hours and Minutes: We begin by iterating over possible hours h in descending order from 11 to 0. For each hour, we iterate over possible minutes m from 59 down to 0.
Format Time: For each combination of h and m, format the time as a string t in the "HH:MM" format using t = f"{h:02d}:{m:02d}".
Match Pattern: Check if this formatted time t can be a valid replacement for s. We do that by verifying that all corresponding characters in t and s are equal wherever s has a specific digit (i.e., not a "?"). This comparison is performed using: all(a == b for a, b in zip(s, t) if a != "?").
Return Result: Once a time that meets the conditions is found, it is returned immediately as it is the latest possible valid time due to our enumeration order.

This approach guarantees that we identify the optimal solution by leveraging the constraints of time formatting and exhaustive search within a bounded range of possibilities.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider the input string s = "?5:4?". Our task is to fill in the "?" characters to form the latest valid 12-hour format time. Here's the step-by-step process using the solution approach described above:

Loop Through Hours and Minutes:
- Start with the largest hour h = 11 and go downwards to 0.
- For each hour, start with the largest minute m = 59 and go downwards to 0.
Format Time:
- Starting with h = 11 and m = 59, format the time as t = "11:59".
Match Pattern:
- Compare t = "11:59" with s = "?5:4?".
- Check each character:
  - '1' in t against '?' in s — they match since '?' can be any digit.
  - '1' in t against '5' in s — no match, move to the next possible minute m = 58.
Continue Matching:
- Try t = "11:58" against s = "?5:4?", but it does not match.
- Continue decrementing minutes until finding a match.
Find Matching Time:
- When m = 45, t = "10:45":
  - '1' in t is compatible with '?' in s.
  - '0' in t is compatible with '5' in s — no match.
- Keep trying until m = 49, t = "05:49":
  - '0' in t matches '?' in s.
  - '5' in t matches '5' in s.
  - ':' matches ':'.
  - '4' matches '4' in s.
  - '9' in t matches '?' in s.
- All characters where s is not '?' are confirmed, hence, t = "05:49" can be returned.

Following these steps ensures that t = "05:49" is the latest possible valid time matching s = "?5:4?".

Solution Implementation

1class Solution:
2    def findLatestTime(self, s: str) -> str:
3        # Iterate over possible hours from 11 to 0 in reverse order
4        for hour in range(11, -1, -1):
5            # Iterate over possible minutes from 59 to 0 in reverse order
6            for minute in range(59, -1, -1):
7                # Format the time string as HH:MM
8                time = f"{hour:02d}:{minute:02d}"
9                # Check if each character in `s` matches `time` where `s` is not "?"
10                if all(char_s == char_t for char_s, char_t in zip(s, time) if char_s != "?"):
11                    return time  # Return the latest time that matches the pattern
12

1class Solution {
2    public String findLatestTime(String s) {
3        // Loop through each possible hour in descending order
4        for (int hour = 11; hour >= 0; hour--) {
5            // Loop through each possible minute in descending order
6            for (int minute = 59; minute >= 0; minute--) {
7              
8                // Format the current time as a string in "HH:MM" format
9                String currentTime = String.format("%02d:%02d", hour, minute);
10              
11                // Assume the current time is a valid solution
12                boolean isValid = true;
13
14                // Check each character position in the input string
15                for (int i = 0; i < s.length(); i++) {
16                    // If the input character is not a '?', ensure it matches the corresponding character in the formatted time
17                    if (s.charAt(i) != '?' && s.charAt(i) != currentTime.charAt(i)) {
18                        isValid = false; // If there's a mismatch, mark the time as invalid
19                        break; // Exit the loop early since the time is not valid
20                    }
21                }
22
23                // If all positions either matched or were '?', return the current time as the result
24                if (isValid) {
25                    return currentTime;
26                }
27            }
28        }
29        return ""; // Fallback return statement (in this logic, unreachable because a solution will always be found)
30    }
31}
32

1#include <string>
2#include <cstdio> // Needed for sprintf
3
4class Solution {
5public:
6    // Function to find the latest possible time by replacing '?' in the input string
7    std::string findLatestTime(std::string s) {
8        // Loop over possible hours from 11 down to 0
9        for (int hour = 11; ; hour--) {
10            // Loop over possible minutes from 59 down to 0
11            for (int minute = 59; minute >= 0; minute--) {
12                char timeStr[6]; // Array to store formatted time string
13                // Format the current hour and minute into a "HH:MM" string
14                sprintf(timeStr, "%02d:%02d", hour, minute);
15              
16                bool isMatch = true; // Flag to determine if the current time matches the pattern
17                // Check each character in the input string
18                for (int i = 0; i < s.length(); i++) {
19                    // If the character is not '?' and does not match the corresponding character in timeStr
20                    if (s[i] != '?' && s[i] != timeStr[i]) {
21                        isMatch = false;
22                        break; // Exit the loop if the pattern does not match
23                    }
24                }
25                // If the time matches the pattern, return it as the result
26                if (isMatch) {
27                    return timeStr;
28                }
29            }
30        }
31    }
32};
33

1// Function to find the latest possible time matching the given pattern
2function findLatestTime(s: string): string {
3    // Iterate over possible hours starting from 11 and decreasing
4    for (let h = 11; ; h--) {
5        // Iterate over possible minutes from 59 down to 0
6        for (let m = 59; m >= 0; m--) {
7            // Create a time string in 'hh:mm' format
8            const timeString: string = `${h.toString().padStart(2, '0')}:${m.toString().padStart(2, '0')}`;
9            let isTimeMatch: boolean = true;
10          
11            // Check if timeString fits the pattern provided in s
12            for (let i = 0; i < s.length; i++) {
13                // If the current character of s is not '?' and does not match the corresponding character in timeString
14                if (s[i] !== '?' && s[i] !== timeString[i]) {
15                    isTimeMatch = false;
16                    break;
17                }
18            }
19          
20            // If a matching time is found, return it
21            if (isTimeMatch) {
22                return timeString;
23            }
24        }
25    }
26}
27

Time and Space Complexity

The time complexity of the code is O(h * m), where h = 12 and m = 60. This complexity arises because there is a nested loop: the outer loop iterates over hours from 11 to 0, and the inner loop iterates over minutes from 59 to 0. For each combination of h and m, the code checks if the non-'?' characters in s match with the formatted time string t, which takes constant time due to the fixed maximum string length of 5 characters.

The space complexity is O(1), as the algorithm only uses a fixed amount of additional memory, regardless of the size of the input, primarily for variables like h, m, t, and their respective loop and conditional checks.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First Search

Breadth First Search

I don’t know