LeetCode 3114 - Latest Time You Can Obtain After Replacing Characters

The problem gives us a string representing a time in 12-hour format using the pattern "HH:MM". Some characters may already be fixed digits, while others are replaced with "?". Our task is to replace every "?

leetcodeeasystringenumeration

LeetCode Problem 3114

Difficulty: 🟢 Easy
Topics: String, Enumeration

Solution

Problem Understanding

The problem gives us a string representing a time in 12-hour format using the pattern "HH:MM". Some characters may already be fixed digits, while others are replaced with "?". Our task is to replace every "?" with a digit so that the resulting time is both valid and as large as possible chronologically.

The valid hour range is from "00" to "11", unlike the more common 24-hour clock. The valid minute range is from "00" to "59".

For example:

  • "1?:?4" can become "10:04", "11:14", "11:54", and many others.
  • Among all valid possibilities, "11:54" is the latest time, so that is the correct answer.

The input size is extremely small because the string always has length 5. This means efficiency is not a major concern, but the challenge is correctly handling all combinations of hour digits while respecting the valid 12-hour constraints.

A few important edge cases immediately stand out:

  • Both hour digits could be unknown, such as "??:45".
  • The first hour digit may restrict the second, such as "1?:30" where the second digit can only go up to 1.
  • The minute digits must stay within 00 to 59.
  • The problem guarantees that at least one valid answer exists, so we never need to handle impossible inputs.

A naive implementation can easily make mistakes when deciding the largest valid hour. For example, greedily placing 9 everywhere does not work because "19:59" is invalid in this problem.

Approaches

Brute Force Approach

The most direct solution is to try every valid time from "11:59" down to "00:00" and check whether it matches the pattern.

For each candidate time:

  1. Format the hour and minute into "HH:MM".
  2. Compare it against the input string.
  3. Every non-"?" character must match exactly.
  4. The first valid match encountered is the latest possible time.

This approach is guaranteed to work because there are only 12 × 60 = 720 possible valid times.

Although this solution is completely acceptable for the constraints, it does more work than necessary because we can determine the optimal digits directly without enumerating all possibilities.

Optimal Greedy Approach

The key observation is that we always want the largest valid digit at every position while maintaining a valid time.

The minute digits are straightforward:

  • The tens place of minutes can be at most 5.
  • The ones place of minutes can be at most 9.

The hour digits require more care because the valid range is only "00" to "11".

For the hour:

  • If the first digit is "?", we prefer '1' whenever possible because it produces a larger hour.
  • If the second digit is also "?", then "11" is the largest valid hour.
  • If the first digit is fixed as '1', then the second digit can only be '0' or '1'.
  • If the first digit is '0', the second digit can be as large as '9'.

Since each position can be optimized independently once the constraints are understood, a greedy construction produces the optimal answer directly.

Approach Time Complexity Space Complexity Notes
Brute Force O(720) O(1) Checks every valid time from latest to earliest
Optimal O(1) O(1) Greedily fills each position with the largest valid digit

Algorithm Walkthrough

  1. Convert the string into a mutable character array because strings are immutable in Python.
  2. Process the first hour digit, s[0].

If it is "?", we want to place '1' whenever possible because valid hours only go up to 11.

  • If the second hour digit is also "?", choose '1'.
  • If the second hour digit is '0' or '1', we can still choose '1'.
  • Otherwise, choose '0'.
  1. Process the second hour digit, s[1].

If it is "?":

  • If the first hour digit is '1', the largest valid second digit is '1'.
  • Otherwise, the largest valid second digit is '9'.
  1. Process the tens digit of minutes, s[3].

If it is "?", replace it with '5' because valid minutes range from 00 to 59. 5. Process the ones digit of minutes, s[4].

If it is "?", replace it with '9'. 6. Join the characters back into a string and return the result.

Why it works

The algorithm works because each position is filled with the largest digit that still allows a valid final time. Since earlier positions are more significant than later ones, maximizing them greedily guarantees the lexicographically and chronologically largest valid time. The constraints on the hour digits ensure that every greedy choice remains valid.

Python Solution

class Solution:
    def findLatestTime(self, s: str) -> str:
        chars = list(s)

        # Fill first hour digit
        if chars[0] == '?':
            if chars[1] == '?' or chars[1] <= '1':
                chars[0] = '1'
            else:
                chars[0] = '0'

        # Fill second hour digit
        if chars[1] == '?':
            if chars[0] == '1':
                chars[1] = '1'
            else:
                chars[1] = '9'

        # Fill minute tens digit
        if chars[3] == '?':
            chars[3] = '5'

        # Fill minute ones digit
        if chars[4] == '?':
            chars[4] = '9'

        return ''.join(chars)

The implementation closely follows the greedy strategy described earlier.

The string is first converted into a list of characters so individual positions can be modified directly.

The hour digits are handled first because they have the strictest constraints. The first hour digit depends on the value of the second digit, so it must be processed carefully. Once the first digit is fixed, determining the second digit becomes straightforward.

The minute digits are much simpler because their valid ranges are independent:

  • The tens digit can never exceed 5.
  • The ones digit can always be 9.

Finally, the character list is joined back into a string and returned.

Go Solution

func findLatestTime(s string) string {
    chars := []byte(s)

    // Fill first hour digit
    if chars[0] == '?' {
        if chars[1] == '?' || chars[1] <= '1' {
            chars[0] = '1'
        } else {
            chars[0] = '0'
        }
    }

    // Fill second hour digit
    if chars[1] == '?' {
        if chars[0] == '1' {
            chars[1] = '1'
        } else {
            chars[1] = '9'
        }
    }

    // Fill minute tens digit
    if chars[3] == '?' {
        chars[3] = '5'
    }

    // Fill minute ones digit
    if chars[4] == '?' {
        chars[4] = '9'
    }

    return string(chars)
}

The Go implementation mirrors the Python logic almost exactly.

Since Go strings are immutable, the solution converts the string into a []byte slice so characters can be modified in place efficiently. After all replacements are complete, the byte slice is converted back into a string.

There are no concerns about integer overflow or memory usage because the input size is fixed and extremely small.

Worked Examples

Example 1

Input:

s = "1?:?4"

Initial state:

Position Value
0 '1'
1 '?'
2 ':'
3 '?'
4 '4'

Step-by-step processing:

Step Action Result
Fill second hour digit First digit is '1', so largest valid choice is '1' "11:?4"
Fill minute tens digit Largest valid choice is '5' "11:54"

Final answer:

"11:54"

Example 2

Input:

s = "0?:5?"

Initial state:

Position Value
0 '0'
1 '?'
2 ':'
3 '5'
4 '?'

Step-by-step processing:

Step Action Result
Fill second hour digit First digit is '0', so largest valid choice is '9' "09:5?"
Fill minute ones digit Largest valid choice is '9' "09:59"

Final answer:

"09:59"

Complexity Analysis

Measure Complexity Explanation
Time O(1) The string length is fixed at 5 characters
Space O(1) Only a few extra variables are used

The algorithm performs a constant amount of work because the input size never changes. Each character position is examined at most once, and no additional data structures proportional to input size are created.

Test Cases

sol = Solution()

assert sol.findLatestTime("1?:?4") == "11:54"  # Example with mixed unknowns
assert sol.findLatestTime("0?:5?") == "09:59"  # Example with fixed first hour digit

assert sol.findLatestTime("??:??") == "11:59"  # All digits unknown
assert sol.findLatestTime("?1:??") == "11:59"  # First hour digit can still be 1
assert sol.findLatestTime("?9:00") == "09:00"  # First hour digit forced to 0
assert sol.findLatestTime("1?:00") == "11:00"  # Second hour digit limited to 1
assert sol.findLatestTime("00:??") == "00:59"  # Earliest hour with unknown minutes
assert sol.findLatestTime("10:?0") == "10:50"  # Unknown minute tens digit
assert sol.findLatestTime("11:5?") == "11:59"  # Unknown minute ones digit
assert sol.findLatestTime("01:23") == "01:23"  # No unknown characters
Test Why
"1?:?4" Validates mixed hour and minute replacement
"0?:5?" Validates large minute selection
"??:??" Tests fully unknown input
"?1:??" Ensures first hour digit becomes 1 when possible
"?9:00" Ensures first hour digit becomes 0 when required
"1?:00" Validates second hour digit restriction
"00:??" Tests minute maximization only
"10:?0" Tests minute tens replacement
"11:5?" Tests minute ones replacement
"01:23" Ensures unchanged valid input remains unchanged

Edge Cases

One important edge case occurs when both hour digits are unknown, such as "??:45". A careless implementation might incorrectly choose "19:45" because it greedily maximizes each digit independently. However, the valid hour range only goes up to "11". The implementation handles this by explicitly checking the relationship between the two hour digits and constructing "11" instead.

Another tricky case is when the second hour digit forces the first digit to be smaller. For example, in "?9:00", choosing '1' for the first digit would produce "19:00", which is invalid. The implementation correctly detects that '9' is too large for a second digit when the first digit is '1', so it chooses '0' instead.

A third edge case appears when the input already contains a complete valid time with no "?" characters, such as "01:23". Some implementations accidentally overwrite existing digits while trying to maximize the time. This solution only modifies positions that contain "?", preserving all fixed digits exactly as required.