Latest Time You Can Obtain After Replacing Characters

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.

Examples

Example 1

1
2
3
4
5
6
7



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

1
2
3
4
5
6
7



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.

Solution

Method 1 – Greedy Replacement

Intuition

To get the latest valid 12-hour time, we should replace each ? with the largest possible digit that keeps the time valid. For hours, the first digit can be at most 1, and if it’s 1, the second digit can be at most 1. For minutes, the first digit can be at most 5, and the second digit can be at most 9.

Approach

If the first hour digit is ‘?’, set it to ‘1’ if the second digit is ‘?’ or <= ‘1’, else ‘0’.
If the second hour digit is ‘?’, set it to ‘1’ if the first digit is ‘1’, else ‘9’.
If the first minute digit is ‘?’, set it to ‘5’.
If the second minute digit is ‘?’, set it to ‘9’.
Return the constructed string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution {
public:
    string findLatestTime(string s) {
        string ans = s;
        if (ans[0] == '?') ans[0] = (ans[1] == '?' || ans[1] <= '1') ? '1' : '0';
        if (ans[1] == '?') ans[1] = (ans[0] == '1') ? '1' : '9';
        if (ans[3] == '?') ans[3] = '5';
        if (ans[4] == '?') ans[4] = '9';
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func findLatestTime(s string) string {
    ans := []byte(s)
    if ans[0] == '?' {
        if ans[1] == '?' || ans[1] <= '1' {
            ans[0] = '1'
        } else {
            ans[0] = '0'
        }
    }
    if ans[1] == '?' {
        if ans[0] == '1' {
            ans[1] = '1'
        } else {
            ans[1] = '9'
        }
    }
    if ans[3] == '?' { ans[3] = '5' }
    if ans[4] == '?' { ans[4] = '9' }
    return string(ans)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution {
    public String findLatestTime(String s) {
        char[] ans = s.toCharArray();
        if (ans[0] == '?') ans[0] = (ans[1] == '?' || ans[1] <= '1') ? '1' : '0';
        if (ans[1] == '?') ans[1] = (ans[0] == '1') ? '1' : '9';
        if (ans[3] == '?') ans[3] = '5';
        if (ans[4] == '?') ans[4] = '9';
        return new String(ans);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution {
    fun findLatestTime(s: String): String {
        val ans = s.toCharArray()
        if (ans[0] == '?') ans[0] = if (ans[1] == '?' || ans[1] <= '1') '1' else '0'
        if (ans[1] == '?') ans[1] = if (ans[0] == '1') '1' else '9'
        if (ans[3] == '?') ans[3] = '5'
        if (ans[4] == '?') ans[4] = '9'
        return String(ans)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def findLatestTime(self, s: str) -> str:
        ans = list(s)
        if ans[0] == '?':
            ans[0] = '1' if ans[1] == '?' or ans[1] <= '1' else '0'
        if ans[1] == '?':
            ans[1] = '1' if ans[0] == '1' else '9'
        if ans[3] == '?':
            ans[3] = '5'
        if ans[4] == '?':
            ans[4] = '9'
        return ''.join(ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


impl Solution {
    pub fn find_latest_time(s: String) -> String {
        let mut ans: Vec<char> = s.chars().collect();
        if ans[0] == '?' {
            ans[0] = if ans[1] == '?' || ans[1] <= '1' { '1' } else { '0' };
        }
        if ans[1] == '?' {
            ans[1] = if ans[0] == '1' { '1' } else { '9' };
        }
        if ans[3] == '?' { ans[3] = '5'; }
        if ans[4] == '?' { ans[4] = '9'; }
        ans.into_iter().collect()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution {
    findLatestTime(s: string): string {
        const ans = s.split('');
        if (ans[0] === '?') ans[0] = (ans[1] === '?' || ans[1] <= '1') ? '1' : '0';
        if (ans[1] === '?') ans[1] = (ans[0] === '1') ? '1' : '9';
        if (ans[3] === '?') ans[3] = '5';
        if (ans[4] === '?') ans[4] = '9';
        return ans.join('');
    }
}

Complexity

⏰ Time complexity: O(1), since the string is always of fixed length 5.
🧺 Space complexity: O(1), only a few variables are used.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Greedy Replacement#

Intuition#

Approach#

Code#

Complexity#