# Latest Time by Replacing Hidden Digits
**Difficulty:** EASY
[External](https://leetcode.com/problems/latest-time-by-replacing-hidden-digits)
Canonical: https://scaleengineer.com/dsa/problems/latest-time-by-replacing-hidden-digits
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## Problem
You are given a string `time` in the form of ` hh:mm`, where some of the digits in the string are hidden (represented by `?`).

The valid times are those inclusively between `00:00` and `23:59`.

Return _the latest valid time you can get from_ `time` _by replacing the hidden_ _digits_.

**Example 1:**

**Input:** time = "2?:?0"
**Output:** "23:50"
**Explanation:** The latest hour beginning with the digit '2' is 23 and the latest minute ending with the digit '0' is 50.

**Example 2:**

**Input:** time = "0?:3?"
**Output:** "09:39"

**Example 3:**

**Input:** time = "1?:22"
**Output:** "19:22"

**Constraints:**

* `time` is in the format `hh:mm`.
* It is guaranteed that you can produce a valid time from the given string.

# Approaches
## Brute-force by Checking All Times
This approach involves iterating through all possible valid times in a day, from the latest (23:59) to the earliest (00:00). For each time, we check if it can be formed from the input pattern. The first time that matches the pattern is the answer, as we are iterating downwards.
**Time:** O(1). The loops run a fixed number of times (24 * 60 = 1440). Inside the loop, the `matches` function and string formatting take constant time. The total number of operations is constant regardless of the input string's content (since its format is fixed). · **Space:** O(1). We only use a few variables to store the current time being checked.
**Pros:** Simple to understand and implement.; Guaranteed to be correct because it exhaustively checks all possibilities in the correct order.
**Cons:** Inefficient in terms of the number of operations. It performs up to 1440 iterations and comparisons, even though a direct solution is possible.
### Explanation
We can systematically check every minute of the day, starting from 23:59 and going down to 00:00. For each time (e.g., "23:59"), we create its string representation. We then compare this generated time string with the input `time` string character by character. A generated time is a "match" if for every position `i` from 0 to 4, either `generated_time.charAt(i) == time.charAt(i)` or `time.charAt(i) == '?'`. Since we are iterating from the latest possible time downwards, the very first match we find will be the latest valid time that can be formed. The problem guarantees that a valid time can always be produced, so we are sure to find a match.

```java
class Solution {
    public String latestTimeByReplacingHiddenDigits(String time) {
        for (int h = 23; h >= 0; h--) {
            for (int m = 59; m >= 0; m--) {
                String currentTime = String.format("%02d:%02d", h, m);
                if (matches(currentTime, time)) {
                    return currentTime;
                }
            }
        }
        return ""; // Should not be reached based on problem constraints
    }

    private boolean matches(String currentTime, String pattern) {
        for (int i = 0; i < 5; i++) {
            if (pattern.charAt(i) != '?' && pattern.charAt(i) != currentTime.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Loop for `hour` from 23 down to 0.
- Inside this loop, loop for `minute` from 59 down to 0.
- Format the current `hour` and `minute` into a `hh:mm` string. For example, if `hour` is 9 and `minute` is 5, the string is "09:05".
- Create a boolean flag `match` and set it to `true`.
- Compare this formatted time string with the input `time` string character by character.
- A generated time is a "match" if for every position `i`, either `generated_time[i] == input_time[i]` or `input_time[i] == '?'`.
- If `match` is still `true` after all checks, we have found the latest possible time. Return the formatted time string.

## Greedy Direct Construction
A more efficient approach is to construct the latest time directly using a greedy strategy. We fill in the '?' characters from left to right (most significant digit to least significant) with the largest possible valid values.
**Time:** O(1). We perform a single pass over the 5 characters of the string. The number of operations is constant. · **Space:** O(1). We use a character array of a fixed size (5) to build the result.
**Pros:** Extremely efficient with a minimal number of operations.; Directly constructs the result without unnecessary iterations or checks.
**Cons:** The logic involves several conditional checks which can be tricky to get right on the first try.
### Explanation
To get the latest time, we want to maximize the hour first, and then the minute. This means we should try to make the digits `h1`, `h2`, `m1`, `m2` as large as possible, in that order of priority. We can convert the input string to a character array to modify it in place.

**Hour:**
- For the first hour digit (`time[0]`): If it's a '?', its value depends on the second digit (`time[1]`). To maximize the hour, we want to use '2' if possible. This is possible if `time[1]` is '?', '0', '1', '2', or '3'. If `time[1]` is '4' or greater, the first digit can't be '2' (as 24 is an invalid hour), so it must be '1'.
- For the second hour digit (`time[1]`): If it's a '?', its value depends on the first digit (`time[0]`). If `time[0]` is '2', the latest `time[1]` can be is '3'. If `time[0]` is '0' or '1', the latest `time[1]` can be is '9'.

**Minute:**
- For the first minute digit (`time[3]`): If it's a '?', the largest valid digit is '5' (to form minutes 50-59).
- For the second minute digit (`time[4]`): If it's a '?', the largest valid digit is '9'.

After filling all '?'s based on these rules, we convert the character array back to a string.

```java
class Solution {
    public String latestTimeByReplacingHiddenDigits(String time) {
        char[] t = time.toCharArray();

        // Handle hour
        if (t[0] == '?') {
            if (t[1] == '?' || t[1] <= '3') {
                t[0] = '2';
            } else {
                t[0] = '1';
            }
        }
        if (t[1] == '?') {
            if (t[0] == '2') {
                t[1] = '3';
            } else {
                t[1] = '9';
            }
        }

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

        return new String(t);
    }
}
```
### Algorithm
- Convert the input `time` string into a character array `t`.
- **Handle `t[0]` (first hour digit):**
  - If `t[0] == '?'`:
    - If `t[1] == '?'` or `t[1] <= '3'`, set `t[0] = '2'`.
    - Else, set `t[0] = '1'`.
- **Handle `t[1]` (second hour digit):**
  - If `t[1] == '?'`:
    - If `t[0] == '2'`, set `t[1] = '3'`.
    - Else, set `t[1] = '9'`.
- **Handle `t[3]` (first minute digit):**
  - If `t[3] == '?'`, set `t[3] = '5'`.
- **Handle `t[4]` (second minute digit):**
  - If `t[4] == '?'`, set `t[4] = '9'`.
- Convert the character array `t` back to a string and return it.

# Solutions
### Java

```java
class Solution {
public
  String maximumTime(String time) {
    char[] t = time.toCharArray();
    if (t[0] == '?') {
      t[0] = t[1] >= '4' && t[1] <= '9' ? '1' : '2';
    }
    if (t[1] == '?') {
      t[1] = t[0] == '2' ? '3' : '9';
    }
    if (t[3] == '?') {
      t[3] = '5';
    }
    if (t[4] == '?') {
      t[4] = '9';
    }
    return new String(t);
  }
}

```

### JavaScript

```javascript
/** * @param {string} time * @return {string} */ var maximumTime = function (
  time,
) {
  const t = Array.from(time);
  if (t[0] === " ? ") {
    t[0] = t[1] >= " 4 " && t[1] <= " 9 " ? " 1 " : " 2 ";
  }
  if (t[1] === " ? ") {
    t[1] = t[0] == " 2 " ? " 3 " : " 9 ";
  }
  if (t[3] === " ? ") {
    t[3] = " 5 ";
  }
  if (t[4] === " ? ") {
    t[4] = " 9 ";
  }
  return t.join("");
};

```

### CPP

```cpp
class Solution {
public:
  string maximumTime(string time) {
    if (time[0] == '?') {
      time[0] = (time[1] >= '4' && time[1] <= '9') ? '1' : '2';
    }
    if (time[1] == '?') {
      time[1] = (time[0] == '2') ? '3' : '9';
    }
    if (time[3] == '?') {
      time[3] = '5';
    }
    if (time[4] == '?') {
      time[4] = '9';
    }
    return time;
  }
};

```

### Python

```python
class Solution:
    def maximumTime(self, time: str) -> str: t = list(time) if t[0] == '?': t[0] = '1' if '4' <= t[1] <= '9' else '2' if t[1] == '?': t[1] = '3' if t[0] == '2' else '9' if t[3] == '?': t[3] = '5' if t[4] == '?': t[4] = '9' return '' . join(t)

```