Tejav
#1736

Latest Time by Replacing Hidden Digits

Easy
StringGreedyGreedyString Manipulation
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(1)
💡

Intuition

Time O(n)Space O(1)

The optimal approach directly constructs the latest valid time by strategically replacing '?' based on the constraints of valid hours and minutes. This avoids unnecessary combinations and checks.

⚙️

Algorithm

4 steps
  1. 1Step 1: Split the time string into hours and minutes.
  2. 2Step 2: Replace '?' in the hour part with the largest possible digits while ensuring the hour remains valid (00-23).
  3. 3Step 3: Replace '?' in the minute part with the largest possible digits (00-59).
  4. 4Step 4: Combine the modified hour and minute parts and return the result.
solution.py13 lines
1# Full working Python code
2
3def latestTime(time):
4    hh, mm = time.split(':')
5    if hh[0] == '?':
6        hh = '2' + hh[1] if hh[1] == '?' or hh[1] < '4' else '1' + hh[1]
7    if hh[1] == '?':
8        hh = hh[0] + '3' if hh[0] == '2' else hh[0] + '9'
9    if mm[0] == '?':
10        mm = '5' + mm[1]
11    if mm[1] == '?':
12        mm = mm[0] + '9'
13    return f'{hh}:{mm}'
ℹ

Complexity note: The time complexity is O(n) because we only make a few checks and replacements based on the length of the string. The space complexity is O(1) since we are using a constant amount of space for the hour and minute variables.

  • 1Understanding the constraints of valid time formats is crucial for constructing the solution.
  • 2Directly manipulating the string based on known limits allows for a more efficient solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.