# Latest Time You Can Obtain After Replacing Characters
**Difficulty:** EASY
[External](https://leetcode.com/problems/latest-time-you-can-obtain-after-replacing-characters)
Canonical: https://scaleengineer.com/dsa/problems/latest-time-you-can-obtain-after-replacing-characters
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** String
---
## Problem
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.

# Approaches
## Brute Force with Backtracking
This approach explores all possible ways to replace the '?' characters with digits from '0' to '9'. For each generated time string, it checks for validity (i.e., if it's a real time between 00:00 and 11:59). The latest valid time found among all possibilities is the answer.
**Time:** O(1). Although the complexity is technically O(10^k) where k is the number of '?'s (k <= 4), the input size is fixed. The number of operations is constant but high, around 10^4 recursive calls in the worst case (`??:??`). · **Space:** O(1). The recursion depth is at most 5, which is constant. We also store the character array and the result string, both of constant size.
**Pros:** Conceptually simple and guaranteed to find the correct answer by exploring all possibilities.
**Cons:** Highly inefficient. The number of combinations can be large (up to 10,000).; Performs many unnecessary checks for invalid times (e.g., '99:99').
### Explanation
We can think of this as a search problem. The goal is to find the maximum valid time in the search space of all possible strings.
A recursive function can be used to generate all combinations. The function would take the current index to fill and the partially built time string.
When a '?' is encountered, the function recursively calls itself for each digit from '0' to '9'.
When a full time string is formed (recursion reaches the end), we parse it and check if the hour is between 0 and 11 and the minute is between 0 and 59.
We maintain a global or passed-down variable to keep track of the latest valid time seen so far.
The base case for the recursion is when we have processed all characters of the string.
Since the problem guarantees a solution exists, we will find at least one valid time.
```java
class Solution {
    String latestTime = "";

    public String maximumTime(String time) {
        char[] t = time.toCharArray();
        generate(t, 0);
        return latestTime;
    }

    private void generate(char[] t, int index) {
        if (index == 5) {
            String currentTime = new String(t);
            if (isValid(currentTime)) {
                if (latestTime.isEmpty() || currentTime.compareTo(latestTime) > 0) {
                    latestTime = currentTime;
                }
            }
            return;
        }

        if (t[index] == '?') {
            for (char c = '0'; c <= '9'; c++) {
                t[index] = c;
                generate(t, index + 1);
                t[index] = '?'; // backtrack
            }
        } else {
            generate(t, index + 1);
        }
    }

    private boolean isValid(String time) {
        try {
            int hh = Integer.parseInt(time.substring(0, 2));
            int mm = Integer.parseInt(time.substring(3, 5));
            return hh >= 0 && hh <= 11 && mm >= 0 && mm <= 59;
        } catch (NumberFormatException e) {
            return false;
        }
    }
}
```
### Algorithm
- Create a recursive helper function `generate(char[] timeArray, int index)`.
- The base case for the recursion is when `index` reaches the end of the array (`index == 5`).
- In the base case, convert the character array to a string.
- Validate the generated time string. Check if HH is in [00, 11] and MM is in [00, 59].
- If it's a valid time, compare it with the `latestTime` found so far and update if the current time is later.
- In the recursive step, if `timeArray[index]` is a digit, simply call `generate(timeArray, index + 1)`.
- If `timeArray[index]` is '?', loop through digits '0' to '9'. For each digit, place it at `timeArray[index]`, recursively call `generate(timeArray, index + 1)`, and then backtrack by resetting `timeArray[index]` to '?'.
- Initialize `latestTime` to an empty string and start the process by calling `generate` with the initial time string and index 0.

## Iterate Down from 11:59
A more direct approach is to check all possible valid times, starting from the latest possible (`11:59`) and working backwards to the earliest (`00:00`). The first time we find that matches the input pattern `s` must be the latest possible one.
**Time:** O(1). The loops run a fixed number of times (12 * 60 = 720). Each check is a constant time operation. The total number of operations is constant and significantly less than the brute-force approach. · **Space:** O(1). We only need space for the candidate string and the input pattern array, both of constant size.
**Pros:** More efficient than brute force as it only checks valid times.; Still relatively simple to understand and implement.
**Cons:** In the worst case (e.g., input is `??:??` and we need to find `00:00`, which is not the case here as we need latest), it might iterate through all 720 times.
### Explanation
This method avoids generating invalid times. We iterate through all 720 possible valid 12-hour times (`12 hours * 60 minutes`).
The loop can run from hour `h = 11` down to `0`, and for each hour, from minute `m = 59` down to `0`.
In each iteration, we format the current hour `h` and minute `m` into a `HH:MM` string. For example, if `h=9` and `m=5`, the string is `09:05`.
Then, we check if this candidate time string could be formed from the input `s`. A match occurs if for every character position, either the input has a '?' or the characters are identical.
The first time we find such a match, we have found our answer, and we can immediately return it.
```java
class Solution {
    public String maximumTime(String time) {
        char[] pattern = time.toCharArray();
        for (int h = 11; h >= 0; h--) {
            for (int m = 59; m >= 0; m--) {
                String candidate = String.format("%02d:%02d", h, m);
                if (matches(candidate, pattern)) {
                    return candidate;
                }
            }
        }
        return ""; // Should not be reached based on problem constraints
    }

    private boolean matches(String candidate, char[] pattern) {
        for (int i = 0; i < 5; i++) {
            if (pattern[i] != '?' && pattern[i] != candidate.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Loop through hours `h` from 11 down to 0.
- Inside this loop, loop through minutes `m` from 59 down to 0.
- For each pair `(h, m)`, create a candidate time string in `HH:MM` format.
- Compare this candidate string with the input pattern character by character.
- A character at a given position `i` in the pattern matches the candidate if `pattern[i] == '?'` or `pattern[i] == candidate[i]`.
- If all characters match, the candidate is a possible time. Since we are iterating from latest to earliest, this is the latest possible time. Return it immediately.
- Since the problem guarantees a solution exists, the function will always return within the loops.

## Greedy Direct Construction
The most efficient approach is to construct the latest time directly using a greedy strategy. We can determine the best possible digit for each '?' position by considering the constraints of the 12-hour format, aiming to maximize the time from left to right (hours first, then minutes).
**Time:** O(1). The algorithm performs a fixed number of checks and assignments, regardless of the input pattern. It's a single pass over a fixed-size string. · **Space:** O(1). A character array of size 5 is used, which is constant space.
**Pros:** Extremely efficient with minimal operations.; Simple and elegant logic that directly solves the problem without searching.
**Cons:** Requires careful handling of the logic for the hour digits, as they are dependent on each other.
### Explanation
To get the latest time, we must maximize the hour part first, then the minute part. This means we should make the digits from left to right as large as possible, while respecting the time format rules.
We can process the four digit positions (`s[0]`, `s[1]`, `s[3]`, `s[4]`) one by one.
- **For the hours (HH):**
  - `s[0]` (first hour digit): If it's '?', its value depends on `s[1]`. To maximize the hour, we prefer '1' over '0'. We can set `s[0]` to '1' only if `s[1]` is '?', '0', or '1'. Otherwise, `s[0]` must be '0'.
  - `s[1]` (second hour digit): If it's '?', its value depends on the now-determined `s[0]`. If `s[0]` is '1', the latest `s[1]` can be is '1' (for 11). If `s[0]` is '0', the latest `s[1]` can be is '9' (for 09).
- **For the minutes (MM):**
  - `s[3]` (first minute digit): If it's '?', the largest valid digit is '5' (for 5x minutes).
  - `s[4]` (second minute digit): If it's '?', the largest valid digit is '9'.
This logic directly builds the final string in a single pass.
```java
class Solution {
    public String maximumTime(String time) {
        char[] t = time.toCharArray();

        // Handle HH
        if (t[0] == '?') {
            if (t[1] == '?' || t[1] <= '1') {
                t[0] = '1';
            } else {
                t[0] = '0';
            }
        }

        if (t[1] == '?') {
            if (t[0] == '1') {
                t[1] = '1';
            } else { // t[0] == '0'
                t[1] = '9';
            }
        }

        // Handle MM
        if (t[3] == '?') {
            t[3] = '5';
        }
        if (t[4] == '?') {
            t[4] = '9';
        }

        return new String(t);
    }
}
```
### Algorithm
- Convert the input string to a character array `t` for mutability.
- **Determine `t[0]`:** If `t[0]` is '?', check `t[1]`. If `t[1]` is '?', '0', or '1', set `t[0]` to '1'. Otherwise, set `t[0]` to '0'.
- **Determine `t[1]`:** If `t[1]` is '?', check the (possibly just updated) `t[0]`. If `t[0]` is '1', set `t[1]` to '1'. Otherwise (`t[0]` is '0'), set `t[1]` to '9'.
- **Determine `t[3]`:** If `t[3]` is '?', set it to '5'.
- **Determine `t[4]`:** If `t[4]` is '?', set it to '9'.
- Convert the modified character array back to a string and return it.

# Solutions
### Java

```java
class Solution {
public
  String findLatestTime(String s) {
    for (int h = 11;; h--) {
      for (int m = 59; m >= 0; m--) {
        String t = String.format("%02d:%02d", h, m);
        boolean ok = true;
        for (int i = 0; i < s.length(); i++) {
          if (s.charAt(i) != '?' && s.charAt(i) != t.charAt(i)) {
            ok = false;
            break;
          }
        }
        if (ok) {
          return t;
        }
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  string findLatestTime(string s) {
    for (int h = 11;; h--) {
      for (int m = 59; m >= 0; m--) {
        char t[6];
        sprintf(t, "%02d:%02d", h, m);
        bool ok = true;
        for (int i = 0; i < s.length(); i++) {
          if (s[i] != '?' && s[i] != t[i]) {
            ok = false;
            break;
          }
        }
        if (ok) {
          return t;
        }
      }
    }
  }
};

```

### Python

```python
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 : 02 d } : { m : 02 d } " if all(a == b for a, b in zip(s, t) if a != "?"): return t

```