3114. Latest Time After Replacing Characters Solution

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

Example 1:

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:

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.

Approach overview

Problem Overview: You receive a time string in the format hh:mm where some characters are replaced with '?'. Each '?' can be replaced with a digit. The goal is to produce the latest valid time possible while respecting the constraints of the clock format.

The hours must form a valid value between 00 and 11, and minutes must be between 00 and 59. Because every unknown digit can be chosen freely, the strategy is to maximize the time while keeping the result valid.

Approach 1: Brute Force Simulation (Time: O(1), Space: O(1))

Enumerate every valid time from 11:59 down to 00:00 and check whether it matches the pattern of the input string. A time matches if each digit either equals the corresponding character or the input contains '?' at that position. Once a match is found, return it immediately because the search starts from the latest time.

This works because the total number of possibilities is very small (12 × 60 = 720). Even a full scan is constant time. The approach demonstrates the problem constraints clearly and relies on simple enumeration and string comparison.

Approach 2: Greedy Replacement (Time: O(1), Space: O(1))

The optimal solution replaces each '?' with the largest digit that still keeps the time valid. Start with the hour digits. If the first hour digit is '?', choose '1' when the second digit is '?' or ≤ '1'; otherwise choose '0'. This guarantees the hour does not exceed 11. If the second hour digit is '?', pick '1' when the first digit is '1', otherwise use '9' to maximize values like 09.

For the minutes, the constraints are simpler. Replace the first minute digit with '5' if it is '?', and the last digit with '9'. These are the largest values that keep minutes within 00–59.

The greedy method works because each position has a locally optimal choice that never blocks a larger valid time later. The logic operates directly on the string and performs a few conditional checks. This makes it both faster to implement and easier to reason about than scanning every candidate. The solution mainly involves manipulating a string and applying simple greedy decisions.

Recommended for interviews: The greedy replacement approach is what interviewers typically expect. It shows you understand the constraints of the time format and can derive the maximum valid digit for each position. Mentioning the brute force enumeration first demonstrates problem exploration, but implementing the greedy logic highlights stronger algorithmic thinking.

Approach 1: Greedy Replacement

This approach uses greedy replacement strategy to replace each '?' in the input string. Start with the hour, maximizing its value by checking if the first digit can be 1 or 0. Then, move to the minute where the largest possible digits up to 5 and 9 are used for the tens and unit place respectively.

Python

def latest_time(time):
    result = list(time)
    if result[0] == '?':
        result[0] = '1' if result[1] <= '1' or result[1] == '?' else '0'
    if result[1] == '?':
        result[1] = '1' if result[0] == '1' else '9'
    if result[3] == '?':
        result[3] = '5'
    if result[4] == '?':
        result[4] = '9'
    return "".join(result)

print(latest_time("1?:?4"))  # Outputs: 11:54
print(latest_time("0?:5?"))  # Outputs: 09:59

Java

class Main {
    public static String latestTime(String time) {
        char[] result = time.toCharArray();
        if (result[0] == '?')
            result[0] = (result[1] <= '1' || result[1] == '?') ? '1' : '0';
        if (result[1] == '?')
            result[1] = (result[0] == '1') ? '1' : '9';
        if (result[3] == '?')
            result[3] = '5';
        if (result[4] == '?')
            result[4] = '9';
        return new String(result);
    }
    public static void main(String[] args) {
        System.out.println(latestTime("1?:?4"));  // Outputs: 11:54
        System.out.println(latestTime("0?:5?"));  // Outputs: 09:59
    }
}

C++

#include <iostream>
#include <string>

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

int main() {
    std::cout << latestTime("1?:?4") << std::endl;  // Outputs: 11:54
    std::cout << latestTime("0?:5?") << std::endl;  // Outputs: 09:59
    return 0;
}

JavaScript

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

console.log(latestTime("1?:?4"));  // Outputs: 11:54
console.log(latestTime("0?:5?"));  // Outputs: 09:59

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

char* latestTime(char* time) {
    static char result[6]; // static to return address of local
    strcpy(result, time);

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

int main() {
    printf("%s\n", latestTime("1?:?4"));  // Outputs: 11:54
    printf("%s\n", latestTime("0?:5?"));  // Outputs: 09:59
    return 0;
}

using System;

public class Program {
    public static string LatestTime(string time) {
        char[] result = time.ToCharArray();
        if (result[0] == '?')
            result[0] = (result[1] <= '1' || result[1] == '?') ? '1' : '0';
        if (result[1] == '?')
            result[1] = (result[0] == '1') ? '1' : '9';
        if (result[3] == '?')
            result[3] = '5';
        if (result[4] == '?')
            result[4] = '9';
        return new string(result);
    }
    public static void Main(string[] args) {
        Console.WriteLine(LatestTime("1?:?4"));  // Outputs: 11:54
        Console.WriteLine(LatestTime("0?:5?"));  // Outputs: 09:59
    }
}

In Python, the time string is converted to a list of characters. '? characters are replaced using conditional logic to ensure largest possible time. Results are joined back to a string to return the final time format.

Complexity

Time Complexity: O(1) as it processes a constant-sized list.
Space Complexity: O(1), since operations occur in place.

Try this approach in the editor

Approach 2: Brute Force Simulation

This approach involves enumerating all possible substitutions for '?' with a pre-constructed list of valid times within a 12-hour clock. By iterating through all valid possibilities, it picks the maximum valid time that fits the conditions.

Python

def latest_time(time):
    max_time = "00:00"
    for h in range(12):
        for m in range(60):
            candidate = f"{h:02}:{m:02}"
            valid = all(time[i] == '?' or time[i] == candidate[i] for i in range(5))
            if valid and candidate > max_time:
                max_time = candidate
    return max_time

print(latest_time("0?:5?"))  # Outputs: 09:59

Java

class Main {
    public static String latestTime(String time) {
        String maxTime = "11:59";
        for (int h = 0; h <= 11; h++) {
            for (int m = 0; m <= 59; m++) {
                String candidate = String.format("%02d:%02d", h, m);
                boolean valid = true;
                for (int i = 0; i < 5; i++) {
                    if (time.charAt(i) != '?' && time.charAt(i) != candidate.charAt(i)) {
                        valid = false;
                        break;
                    }
                }
                if (valid && candidate.compareTo(maxTime) > 0) {
                    maxTime = candidate;
                } 
            }
        }
        return maxTime;
    }
    public static void main(String[] args) {
        System.out.println(latestTime("0?:5?"));  // Outputs: 09:59
    }
}

C++

#include <iostream>
#include <string>
#include <algorithm>

std::string latestTime(std::string time) {
    std::string max_time = "11:59";
    for (int h = 0; h <= 11; ++h) {
        for (int m = 0; m <= 59; ++m) {
            std::ostringstream candidate;
            candidate << std::setw(2) << std::setfill('0') << h << ':' << std::setw(2) << std::setfill('0') << m;
            bool valid = true;
            for (int i = 0; i < 5; ++i) {
                if (time[i] != '?' && time[i] != candidate.str()[i]) {
                    valid = false;
                    break;
                }
            }
            if (valid && candidate.str() > max_time) {
                max_time = candidate.str();
            }
        }
    }
    return max_time;
}

int main() {
    std::cout << latestTime("0?:5?") << std::endl;  // Outputs: 09:59
    return 0;
}

JavaScript

function latestTime(time) {
    let maxTime = "00:00";
    for (let h = 0; h <= 11; h++) {
        for (let m = 0; m <= 59; m++) {
            let candidate = ('0'+h).slice(-2)+':' + ('0'+m).slice(-2);
            let valid = [...time].every((char, i) => char === '?' || char === candidate[i]);
            if (valid && candidate > maxTime) {
                maxTime = candidate;
            }
        }
    }
    return maxTime;
}

console.log(latestTime("0?:5?"));  // Outputs: 09:59

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

char* latestTime(char* time) {
    static char result[6];
    char max_time[] = "11:59";

    for (int h1 = 0; h1 <= 1; ++h1) {
        for (int h2 = 0; h2 <= 9; ++h2) {
            if (h1 == 1 && h2 > 1) break;
            for (int m1 = 0; m1 <= 5; ++m1) {
                for (int m2 = 0; m2 <= 9; ++m2) {
                    char candidate[6];
                    sprintf(candidate, "%d%d:%d%d", h1, h2, m1, m2);
                    int valid = 1;
                    for (int i = 0; i < 5; ++i) {
                        if (time[i] != '?' && time[i] != candidate[i]) {
                            valid = 0;
                            break;
                        }
                    }
                    if (valid && strcmp(candidate, max_time) > 0) {
                        strcpy(max_time, candidate);
                    }
                }
            }
        }
    }
    strcpy(result, max_time);
    return result;
}

int main() {
    printf("%s\n", latestTime("0?:5?"));  // Outputs: 09:59
    return 0;
}

using System;
using System.Globalization;

public class Program {
    public static string LatestTime(string time) {
        string maxTime = "11:59";
        for (int h = 0; h <= 11; h++) {
            for (int m = 0; m <= 59; m++) {
                string candidate = string.Format("{0:D2}:{1:D2}", h, m);
                bool valid = true;
                for (int i = 0; i < 5; i++) {
                    if (time[i] != '?' && time[i] != candidate[i]) {
                        valid = false;
                        break;
                    }
                }
                if (valid && String.Compare(candidate, maxTime) > 0) {
                    maxTime = candidate;
                }
            }
        }
        return maxTime;
    }
    public static void Main() {
        Console.WriteLine(LatestTime("0?:5?"));  // Outputs: 09:59
    }
}

The Python solution attempts every permissible time within 12-hours, ensuring chronology and picking the optimal setting. It leverages simple string comparison for maximum time determination and utilizes list comprehension for compact verification.

Complexity

Time Complexity: O(720), iteratively exploring every valid form.
Space Complexity: O(1), as only a minimal number of variables track state.

Try this approach in the editor

Approach 3: Enumeration

We can enumerate all times from large to small, where the hour h ranges from 11 to 0, and the minute m ranges from 59 to 0. For each time t, we check whether each digit of t matches the corresponding digit in s (if the corresponding digit in s is not "?"). If it does, then we have found the answer and return t.

The time complexity is O(h times m), where h = 12 and m = 60. The space complexity is O(1).

TypeScript

function findLatestTime(s: string): string {
    for (let h = 11; ; h--) {
        for (let m = 59; m >= 0; m--) {
            const t: string = `${h.toString().padStart(2, '0')}:${m.toString().padStart(2, '0')}`;
            let ok: boolean = true;
            for (let i = 0; i < s.length; i++) {
                if (s[i] !== '?' && s[i] !== t[i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                return t;
            }
        }
    }
}

func findLatestTime(s string) string {
	for h := 11; ; h-- {
		for m := 59; m >= 0; m-- {
			t := fmt.Sprintf("%02d:%02d", h, m)
			ok := true
			for i := 0; i < len(s); i++ {
				if s[i] != '?' && s[i] != t[i] {
					ok = false
					break
				}
			}
			if ok {
				return t
			}
		}
	}
}

Try this approach in the editor

Approach 4: Judge Each Digit

We can judge each digit of s one by one. If it is "?", we determine the value of this digit based on the characters before and after it. Specifically, we have the following rules:

If s[0] is "?", then the value of s[0] should be "1" or "0", depending on the value of s[1]. If s[1] is "?" or s[1] is less than "2", then the value of s[0] should be "1", otherwise the value of s[0] should be "0".
If s[1] is "?", then the value of s[1] should be "1" or "9", depending on the value of s[0]. If s[0] is "1", then the value of s[1] should be "1", otherwise the value of s[1] should be "9".
If s[3] is "?", then the value of s[3] should be "5".
If s[4] is "?", then the value of s[4] should be "9".

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

TypeScript

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

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

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Replacement	Time Complexity: O(1) as it processes a constant-sized list. Space Complexity: O(1), since operations occur in place.
Brute Force Simulation	Time Complexity: O(720), iteratively exploring every valid form. Space Complexity: O(1), as only a minimal number of variables track state.
Enumeration	–
Judge Each Digit	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Simulation	O(1)	O(1)	Useful for quickly validating the idea or when constraints are extremely small
Greedy Replacement	O(1)	O(1)	Best approach for interviews and production code; directly constructs the maximum valid time

Frequently asked questions

Is Latest Time You Can Obtain After Replacing Characters easy or hard?

Latest Time You Can Obtain After Replacing Characters is classified as an Easy problem. The challenge is understanding the valid hour range and selecting the maximum digit that keeps the time valid. Once those constraints are clear, the greedy implementation is straightforward.

Latest Time You Can Obtain After Replacing Characters Python/Java solution

The greedy approach translates directly to Python, Java, C++, C#, JavaScript, and C. Convert the string to a mutable structure, apply conditional replacements for hour and minute digits, then return the updated string. The implementation typically takes only a few lines.

How to solve Latest Time You Can Obtain After Replacing Characters in O(1)?

Process the string digit by digit and greedily assign the largest valid value. Ensure the hour stays within 00–11 by choosing '1' or '0' for the first digit depending on the second. Fill remaining unknowns with the maximum valid digits, such as '5' and '9' for minutes.

What is the best approach for Latest Time You Can Obtain After Replacing Characters?

Greedy replacement is the best approach. Replace each '?' with the largest possible digit that still keeps the time valid. Handle hour constraints first (00–11), then minutes (00–59). The algorithm runs in O(1) time because the string length is fixed.

Is Latest Time You Can Obtain After Replacing Characters asked at Google/Amazon/Meta?

The problem resembles common interview questions about time formatting, greedy digit selection, and string manipulation. Variants of these problems appear in interviews at companies like Amazon and Google where candidates must reason about constraints and edge cases.

What data structure is used in Latest Time You Can Obtain After Replacing Characters?

The solution mainly uses simple string manipulation. Characters are inspected and replaced directly in the time string while applying greedy rules. No advanced data structures are required beyond basic string or character arrays.

What is the time complexity of Latest Time You Can Obtain After Replacing Characters?

Both common solutions run in constant time. The greedy solution performs a few conditional checks on a fixed-length string, giving O(1) time and O(1) space. Even the brute force method checks at most 720 possible times, which is also constant.

Latest Time You Can Obtain After Replacing Characters solution and explanation

The problem

Approach overview

Approach 1: Greedy Replacement

Approach 2: Brute Force Simulation

Approach 3: Enumeration

Approach 4: Judge Each Digit

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Latest Time You Can Obtain After Replacing Characters solution and explanation

The problem

Approach overview

Approach 1: Greedy Replacement

Approach 2: Brute Force Simulation

Approach 3: Enumeration

Approach 4: Judge Each Digit

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems