Welcome to Subscribe On Youtube

1736. Latest Time by Replacing Hidden Digits

Description

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.

Solutions

Solution 1: Greedy

We process each digit of the string in order, following these rules:

  1. First digit: If the value of the second digit is determined and falls within the range $[4, 9]$, then the first digit can only be $1$. Otherwise, the first digit can be up to $2$.
  2. Second digit: If the value of the first digit is determined and is $2$, then the second digit can be up to $3$. Otherwise, the second digit can be up to $9$.
  3. Third digit: The third digit can be up to $5$.
  4. Fourth digit: The fourth digit can be up to $9$.

The time complexity is $O(1)$, and the space complexity is $O(1)$.

  • 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); } } 
  • 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; } }; 
  • 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) 
  • func maximumTime(time string) string { t := []byte(time) if t[0] == '?' { if t[1] >= '4' && t[1] <= '9' { t[0] = '1' } else { t[0] = '2' } } if t[1] == '?' { if t[0] == '2' { t[1] = '3' } else { t[1] = '9' } } if t[3] == '?' { t[3] = '5' } if t[4] == '?' { t[4] = '9' } return string(t) } 
  • /** * @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(''); };

All Problems

All Solutions