1736. Latest Time by Replacing Hidden Digits Solution

The 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.

Approach overview

Problem Overview: You get a 5‑character time string in the format HH:MM. Some digits are hidden using '?'. Replace every '?' so the final string represents the latest possible valid 24‑hour time.

Approach 1: Use Conditional Replacement (O(1) time, O(1) space)

The time string has a fixed length, so you can directly decide each missing digit using greedy rules. Focus on maximizing the hour first, then the minute. For the first hour digit (H1), choose '2' if the second digit is '?' or ≤ '3'; otherwise use '1'. For the second hour digit (H2), if H1 is '2', the maximum allowed value is '3'; otherwise it can be '9'. Minutes follow simpler constraints: the first minute digit (M1) can be at most '5', and the last digit (M2) can be '9'. Iterate through the characters, apply these rules, and replace each '?' with the highest valid digit. This greedy strategy works because choosing the largest valid digit at each position always leads to the lexicographically largest valid time. The algorithm runs in constant time since the string length never changes. This problem is a straightforward application of greedy reasoning with basic constraints on a string.

Approach 2: Two-Pass Approach with Conditions (O(1) time, O(1) space)

Another clean approach processes the string in two passes: first resolve the hour component, then resolve the minutes. In the first pass, evaluate both hour digits together because their valid range (00–23) creates a dependency. If both are '?', replace them with "23". If only the first digit is missing, choose '2' when the second digit is ≤ '3'; otherwise choose '1'. If only the second digit is missing, check the first digit and assign '3' when it is '2', otherwise '9'. In the second pass, handle the minute portion independently: replace the first minute digit with '5' if missing, and the last with '9'. Separating the logic this way improves readability and mirrors the natural constraint boundaries between hours and minutes. Like the greedy version, this method operates on a constant-sized input, so both time and space complexity remain O(1).

Recommended for interviews: The conditional greedy replacement is what most interviewers expect. It shows you understand the constraints of the 24‑hour clock and can derive the maximum valid digit for each position. The two‑pass variant is equally correct and often easier to reason about during implementation, especially when explaining your logic out loud.

Approach 1: Use Conditional Replacement

This approach uses conditional checks to replace each '?' in the time string with the highest possible digit while maintaining valid time format constraints. We'll replace '?' in hours and minutes step-by-step, ensuring the output is valid. This direct manipulation approach ensures we get the latest possible time.

Python

def maximum_time(time: str) -> str:
    time = list(time)
    if time[0] == '?':
        time[0] = '2' if time[1] == '?' or time[1] <= '3' else '1'
    if time[1] == '?':
        time[1] = '3' if time[0] == '2' else '9'
    if time[3] == '?':
        time[3] = '5'
    if time[4] == '?':
        time[4] = '9'
    return ''.join(time)

# Example usage
print(maximum_time("2?:?0"))

Java

public class TimeReplace {
    public static String maximumTime(String time) {
        char[] result = time.toCharArray();
        if (result[0] == '?') {
            result[0] = (result[1] <= '3' || result[1] == '?') ? '2' : '1';
        }
        if (result[1] == '?') {
            result[1] = (result[0] == '2') ? '3' : '9';
        }
        if (result[3] == '?') {
            result[3] = '5';
        }
        if (result[4] == '?') {
            result[4] = '9';
        }
        return new String(result);
    }

    public static void main(String[] args) {
        String time = "2?:?0";
        System.out.println("Latest time: " + maximumTime(time));
    }
}

C++

#include <iostream>
#include <string>
using namespace std;

string maximumTime(string time) {
    if (time[0] == '?') {
        time[0] = (time[1] <= '3' || time[1] == '?') ? '2' : '1';
    }
    if (time[1] == '?') {
        time[1] = (time[0] == '2') ? '3' : '9';
    }
    if (time[3] == '?') {
        time[3] = '5';
    }
    if (time[4] == '?') {
        time[4] = '9';
    }
    return time;
}

int main() {
    string time = "2?:?0";
    cout << "Latest time: " << maximumTime(time) << endl;
    return 0;
}

JavaScript

function maximumTime(time) {
    let chars = time.split('');
    if (chars[0] === '?') {
        chars[0] = (chars[1] <= '3' || chars[1] === '?') ? '2' : '1';
    }
    if (chars[1] === '?') {
        chars[1] = (chars[0] === '2') ? '3' : '9';
    }
    if (chars[3] === '?') {
        chars[3] = '5';
    }
    if (chars[4] === '?') {
        chars[4] = '9';
    }
    return chars.join('');
}

console.log(maximumTime("2?:?0"));

#include <stdio.h>
#include <string.h>

char* maximumTime(char* time) {
    if (time[0] == '?') {
        time[0] = (time[1] <= '3' || time[1] == '?') ? '2' : '1';
    }
    if (time[1] == '?') {
        time[1] = (time[0] == '2') ? '3' : '9';
    }
    if (time[3] == '?') {
        time[3] = '5';
    }
    if (time[4] == '?') {
        time[4] = '9';
    }
    return time;
}

int main() {
    char time[] = "2?:?0";
    printf("Latest time: %s\n", maximumTime(time));
    return 0;
}

using System;

public class TimeReplace {
    public static string MaximumTime(string time) {
        char[] chars = time.ToCharArray();
        if (chars[0] == '?')
            chars[0] = (chars[1] <= '3' || chars[1] == '?') ? '2' : '1';
        if (chars[1] == '?')
            chars[1] = (chars[0] == '2') ? '3' : '9';
        if (chars[3] == '?')
            chars[3] = '5';
        if (chars[4] == '?')
            chars[4] = '9';
        return new string(chars);
    }

    public static void Main() {
        string time = "2?:?0";
        Console.WriteLine("Latest time: " + MaximumTime(time));
    }
}

This Python solution adopts a similar method where the string is converted to a list for mutability. The logic is analogous to the preceding solutions: each '?' is strategically replaced by the maximum numeric value compliant with a valid time.

Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Two-Pass Approach with Conditions

This approach divides the replacement operations into two distinct passes. First, it replaces the hours based on possible constraints, then finalizes the replacements for minutes, ensuring all components align with valid time rules.

Python

def maximum_time(time: str) -> str:
    time = list(time)
    if time[0] == '?':
        time[0] = '2' if time[1] == '?' or time[1] <= '3' else '1'
    if time[1] == '?':
        time[1] = '3' if time[0] == '2' else '9'

    # Adjust minutes
    if time[3] == '?':
        time[3] = '5'
    if time[4] == '?':
        time[4] = '9'

    return ''.join(time)

# Example
print(maximum_time("2?:?0"))

Java

public class Main {
    public static String maximumTime(String time) {
        char[] result = time.toCharArray();

        // First pass for hour
        if (result[0] == '?') result[0] = (result[1] <= '3' || result[1] == '?') ? '2' : '1';
        if (result[1] == '?') result[1] = (result[0] == '2') ? '3' : '9';

        // Second pass for minute
        if (result[3] == '?') result[3] = '5';
        if (result[4] == '?') result[4] = '9';

        return new String(result);
    }

    public static void main(String[] args) {
        String time = "2?:?0";
        System.out.println("Latest time: " + maximumTime(time));
    }
}

C++

#include <iostream>
#include <string>
using namespace std;

string maximumTime(string time) {
    // First pass for hours
    if (time[0] == '?') time[0] = (time[1] <= '3' || time[1] == '?') ? '2' : '1';
    if (time[1] == '?') time[1] = (time[0] == '2') ? '3' : '9';

    // Second pass for minutes
    if (time[3] == '?') time[3] = '5';
    if (time[4] == '?') time[4] = '9';

    return time;
}

int main() {
    string time = "2?:?0";
    cout << "Latest time: " << maximumTime(time) << endl;
    return 0;
}

JavaScript

function maximumTime(time) {
    let chars = time.split('');
    if (chars[0] === '?') {
        chars[0] = (chars[1] <= '3' || chars[1] === '?') ? '2' : '1';
    }
    if (chars[1] === '?') {
        chars[1] = (chars[0] === '2') ? '3' : '9';
    }
    if (chars[3] === '?') {
        chars[3] = '5';
    }
    if (chars[4] === '?') {
        chars[4] = '9';
    }
    return chars.join('');
}

console.log(maximumTime("2?:?0"));

#include <stdio.h>
#include <string.h>

char* maximumTime(char* time) {
    if (time[0] == '?') time[0] = (time[1] <= '3' || time[1] == '?') ? '2' : '1';
    if (time[1] == '?') time[1] = (time[0] == '2') ? '3' : '9';
    
    // Minutes adjustment
    if (time[3] == '?') time[3] = '5';
    if (time[4] == '?') time[4] = '9';
    return time;
}

int main() {
    char time[] = "2?:?0";
    printf("Latest time: %s\n", maximumTime(time));
    return 0;
}

using System;

class Program {
    public static string MaximumTime(string time) {
        char[] chars = time.ToCharArray();
        if (chars[0] == '?')
            chars[0] = (chars[1] <= '3' || chars[1] == '?') ? '2' : '1';
        if (chars[1] == '?')
            chars[1] = (chars[0] == '2') ? '3' : '9';

        // Finalize minutes
        if (chars[3] == '?')
            chars[3] = '5';
        if (chars[4] == '?')
            chars[4] = '9';

        return new string(chars);
    }

    static void Main() {
        string time = "2?:?0";
        Console.WriteLine("Latest time: " + MaximumTime(time));
    }
}

Utilizing Python, the solution administers a dual pass: the first accommodates potential variations in hour digits; the second secures the max possible minute digits, fostering logical progression and operational completion.

Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Greedy

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

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.
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.
Third digit: The third digit can be up to 5.
Fourth digit: The fourth digit can be up to 9.

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

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)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Use Conditional Replacement	Time Complexity: O(1) Space Complexity: O(1)
Two-Pass Approach with Conditions	Time Complexity: O(1) Space Complexity: O(1)
Greedy	–

Complexity analysis

Approach	Time	Space	When to Use
Conditional Greedy Replacement	O(1)	O(1)	Best general solution. Directly computes the maximum valid time using digit constraints.
Two-Pass Approach with Conditions	O(1)	O(1)	Useful when you want clearer separation between hour and minute logic for readability.

Frequently asked questions

Is Latest Time by Replacing Hidden Digits easy or hard?

Latest Time by Replacing Hidden Digits is classified as an Easy problem. The challenge lies in understanding the constraints of the 24‑hour clock and applying greedy logic to choose the maximum valid digit for each position.

Latest Time by Replacing Hidden Digits Python/Java solution

In Python or Java, convert the string to a mutable character array and replace '?' based on position rules. Apply greedy checks for the hour digits (00–23) and minute digits (00–59). After replacements, convert the array back to a string and return the resulting time.

How to solve Latest Time by Replacing Hidden Digits in O(1)?

Scan the time string and greedily replace each '?' with the largest digit allowed by the 24‑hour format. The first hour digit can be '2' or '1' depending on the second digit, the second hour digit depends on whether the first is '2', the first minute digit can be '5', and the last minute digit can be '9'. Because the string size never changes, the solution runs in constant time.

What is the best approach for Latest Time by Replacing Hidden Digits?

The most efficient approach is greedy conditional replacement. For each '?' digit, choose the maximum value that still forms a valid 24‑hour time. Because the string length is fixed (HH:MM), the algorithm runs in O(1) time and O(1) space while guaranteeing the latest valid result.

Is Latest Time by Replacing Hidden Digits asked at Google/Amazon/Meta?

Problems involving time formatting and greedy digit replacement appear frequently in interviews at large tech companies. While this exact question is most commonly seen in coding practice platforms, the pattern of constraint‑based string manipulation is relevant to interviews at companies like Amazon and Google.

What data structure is used in Latest Time by Replacing Hidden Digits?

The solution mainly uses string or character array manipulation. No complex data structures are required; the logic relies on conditional checks and greedy digit selection based on the constraints of a valid 24‑hour time.

What is the time complexity of Latest Time by Replacing Hidden Digits?

The time complexity is O(1). The input always has exactly five characters (HH:MM), so the algorithm performs a constant number of checks and replacements regardless of input. Space complexity is also O(1) since the modification happens directly on the string or a small character array.

Latest Time by Replacing Hidden Digits solution and explanation

The problem

Approach overview

Approach 1: Use Conditional Replacement

Approach 2: Two-Pass Approach with Conditions

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Latest Time by Replacing Hidden Digits solution and explanation

The problem

Approach overview

Approach 1: Use Conditional Replacement

Approach 2: Two-Pass Approach with Conditions

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems