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.

Examples

Example 1

1
2
3

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

1
2

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

Example 3

1
2

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.

Solution

Method 1 – Greedy Replacement

Intuition

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

Approach

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    string maximumTime(string time) {
        string ans = time;
        if (ans[0] == '?') ans[0] = (ans[1] == '?' || ans[1] <= '3') ? '2' : '1';
        if (ans[1] == '?') ans[1] = (ans[0] == '2') ? '3' : '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 maximumTime(time string) string {
    ans := []byte(time)
    if ans[0] == '?' {
        if ans[1] == '?' || ans[1] <= '3' {
            ans[0] = '2'
        } else {
            ans[0] = '1'
        }
    }
    if ans[1] == '?' {
        if ans[0] == '2' {
            ans[1] = '3'
        } 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 maximumTime(String time) {
        char[] ans = time.toCharArray();
        if (ans[0] == '?') ans[0] = (ans[1] == '?' || ans[1] <= '3') ? '2' : '1';
        if (ans[1] == '?') ans[1] = (ans[0] == '2') ? '3' : '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 maximumTime(time: String): String {
        val ans = time.toCharArray()
        if (ans[0] == '?') ans[0] = if (ans[1] == '?' || ans[1] <= '3') '2' else '1'
        if (ans[1] == '?') ans[1] = if (ans[0] == '2') '3' 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 maximumTime(self, time: str) -> str:
        ans = list(time)
        if ans[0] == '?':
            ans[0] = '2' if ans[1] == '?' or ans[1] <= '3' else '1'
        if ans[1] == '?':
            ans[1] = '3' if ans[0] == '2' 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 maximum_time(time: String) -> String {
        let mut ans: Vec<char> = time.chars().collect();
        if ans[0] == '?' {
            ans[0] = if ans[1] == '?' || ans[1] <= '3' { '2' } else { '1' };
        }
        if ans[1] == '?' {
            ans[1] = if ans[0] == '2' { '3' } 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 {
    maximumTime(time: string): string {
        const ans = time.split('');
        if (ans[0] === '?') ans[0] = (ans[1] === '?' || ans[1] <= '3') ? '2' : '1';
        if (ans[1] === '?') ans[1] = (ans[0] === '2') ? '3' : '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.