algoadvance

Leetcode 3114. Latest Time You Can Obtain After Replacing Characters

Problem Statement

You are given a string time in the format of “hh:mm”, where some of the digits in the string may be replaced by ? (question mark). The valid times are in the range of “00:00” to “23:59”. Return the latest valid time you can obtain by replacing the ? with digits.

Example:

Clarifying Questions

  1. Input Constraints:
    • Is the input guaranteed to follow the “hh:mm” format?
    • Should we consider just cases within the range “00:00” to “23:59”?
  2. Edge Cases:
    • What is the behavior if time contains no ??
    • Should we handle multiple ? in any particular sequence?

Strategy

  1. Identify the Positions:
    • time[0]: First digit of the hour.
    • time[1]: Second digit of the hour.
    • time[3]: First digit of the minute.
    • time[4]: Second digit of the minute.
  2. Replace Characters from Left to Right for Maximum Value:
    • For time[0]:
      • Can be ‘2’ if time[1] is either ‘?’ or in the range ‘0’-‘3’.
      • Otherwise, ‘1’.
    • For time[1]:
      • If time[0] is ‘2’, time[1] can be in the range ‘0’-‘3’.
      • Otherwise, it can be ‘9’.
    • For time[3]: Regardless of the hour, it can be ‘5’.
    • For time[4]: Regardless of other digits, it can be ‘9’.

Code

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

string maximumTime(string time) {
    // Handle the hours part
    if (time[0] == '?') {
        time[0] = (time[1] == '?' || time[1] <= '3') ? '2' : '1';
    }
    if (time[1] == '?') {
        time[1] = (time[0] == '2') ? '3' : '9';
    }

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

    return time;
}

// Example usage
int main() {
    string time = "2?:?0";
    cout << "Latest time: " << maximumTime(time) << endl; // Output: "23:50"
    return 0;
}

Time Complexity

The time complexity of this solution is O(1), which means it runs in constant time regardless of the input. This efficiency is due to the fixed number of operations we perform since time will always have a fixed length of 5 characters.

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