algoadvance

Leetcode 1736. Latest Time by Replacing Hidden Digits

Problem Statement

You are given a string time in the form of “HH:MM”, where some of the digits in the string are represented by ‘?’. The question marks represent digits that need to be replaced to convert time into the latest possible valid 24-hour time. Return the latest valid time in the “HH:MM” format.

Clarifying Questions

  1. Range of Time:
    • The time is in a 24-hour format, so hours can range from 00 to 23 and minutes from 00 to 59.
  2. Input Format:
    • The input will always be exactly 5 characters long, in the format “HH:MM”, where each ‘H’ or ‘M’ can be a digit [0-9] or ‘?’.
  3. Output Format:
    • The output should be a string in the same format “HH:MM”.

Strategy

To find the latest valid time by replacing ‘?’, we need to consider the following:

  1. Hour Formatting:
    • For the first digit of hours (time[0]):
      • If the second digit (time[1]) is between '0' and '3' (inclusive), the first digit can be 2 to maximize.
      • Otherwise, to avoid invalid hours, the first digit should be 1.
    • For the second digit of hours (time[1]):
      • If the first digit is 2, the second digit can be between 0 and 3.
      • Otherwise, the second digit should be 9.
  2. Minute Formatting:
    • For the first digit of minutes (time[3]), the maximum possible value is 5.
    • For the second digit of minutes (time[4]), the maximum value is 9.

Code

#include <iostream>
#include <string>

std::string maximumTime(std::string time) {
    // Process hours
    if (time[0] == '?') {
        if (time[1] != '?' && time[1] > '3') {
            time[0] = '1';
        } else {
            time[0] = '2';
        }
    }
    if (time[1] == '?') {
        if (time[0] == '2') {
            time[1] = '3';
        } else {
            time[1] = '9';
        }
    }

    // Process minutes
    if (time[3] == '?') {
        time[3] = '5';
    }
    if (time[4] == '?') {
        time[4] = '9';
    }

    return time;
}

int main() {
    std::string time;
    std::cin >> time;
    std::cout << maximumTime(time) << std::endl;
    return 0;
}

Time Complexity

The time complexity of this solution is O(1), as the operations to replace the ‘?’ characters involve a constant amount of work regardless of the input size.

This solution maximizes the given time string to the latest possible valid time while ensuring all replacements lead to a valid 24-hour time format.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI