Latest Time You Can Obtain After Replacing Characters

Latest Time You Can Obtain After Replacing Characters - Problem

String Enumeration Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "1?:?9"

› Output: "11:59"

💡 Note: Replace first '?' with '1' to get maximum hour 11, and second '?' with '5' to get maximum minute 59. Result: 11:59 is the latest valid time.

Example 2 — All Question Marks

$ Input: s = "??:??"

› Output: "11:59"

💡 Note: All positions are flexible. Choose maximum valid digits: hour = 11 (max hour), minute = 59 (max minute). Result: 11:59.

Example 3 — Hour Constraint

$ Input: s = "0?:??"

› Output: "09:59"

💡 Note: First hour digit is 0, so second can be at most 9 (giving 09). Minutes can be maximized to 59. Result: 09:59.

Constraints

s.length == 5
s[2] == ':'
All other characters in s are digits or '?'

Visualization

Tap to expand

Understanding the Visualization

Input

Time string with '?' characters: "1?:?9"

Process

Replace each '?' with the largest valid digit

Output

Latest valid time: "11:59"

Key Takeaway

🎯 Key Insight: Use greedy strategy - each position independently chooses the maximum valid digit

Asked in

G Google 15 a Amazon 12

The key insight is to use a greedy approach, choosing the maximum valid digit for each position. The greedy approach works optimally because each position has clear constraints. Time: O(1), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Approach - Position by Position	O(1)	O(1)	Choose the largest valid digit for each position from left to right
Brute Force - Try All Combinations	O(10^k)	O(1)	Generate all possible digit combinations and find the latest valid time

Greedy Approach - Position by Position — Algorithm Steps

Process each position from left to right
For each '?', try the largest possible digit (9 down to 0)
Check if the digit maintains time validity
Choose the first valid digit and move to next position

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Hours

Handle first and second hour digits based on constraints

Process Minutes

Maximize minute digits within valid ranges

Result

Construct the latest valid time

Code -

solution.c — C

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

char* solution(char* s) {
    // Position 0: First digit of hour (0 or 1)
    if (s[0] == '?') {
        if (s[1] == '?' || s[1] <= '1') {
            s[0] = '1';  // Can be 1 if second digit allows
        } else {
            s[0] = '0';  // Must be 0 if second digit > 1
        }
    }
    
    // Position 1: Second digit of hour
    if (s[1] == '?') {
        if (s[0] == '1') {
            s[1] = '1';  // 11 is max hour
        } else {
            s[1] = '9';  // 09 is valid
        }
    }
    
    // Position 3: First digit of minute (0-5)
    if (s[3] == '?') {
        s[3] = '5';  // Maximum first digit of minutes
    }
    
    // Position 4: Second digit of minute (0-9)
    if (s[4] == '?') {
        s[4] = '9';  // Maximum second digit of minutes
    }
    
    return s;
}

int main() {
    static char s[6];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    char* result = solution(s);
    printf("%s\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Fixed 5 positions, each position tries at most 10 digits, so O(50) = O(1)

✓ Linear Growth

Space Complexity

O(1)

Only using character array for input modification, no additional data structures

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Approach - Position by Position — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler