algoadvance

Leetcode 1736. Latest Time by Replacing Hidden Digits

Problem Statement

You are given a string time in the format of “HH:MM”, where some of the digits in the string are hidden (represented by ?). The task is to replace each hidden digit with an integer from 0 to 9 such that the resulting time is the latest valid time possible.

Clarifying Questions

1. Q: What will be the length of the input string? A: The input string time will always be of length 5 and in the format “HH:MM”.

2. Q: Will there always be at least one ? in the input string? A: Yes, there will be one or more ? characters in the string.

3. Q: Can the input string be invalid? A: The input string will always be valid in terms of format but will contain ? characters that we need to replace.

Strategy

To find the latest possible time by replacing the ? characters:

1. Start from the leftmost and analyze each character.
2. For the hour component:
   • If time[0] is ?, it can be 2 if time[1] is 0 to 3, otherwise it can be 1 or 0 depending on the valid range.
   • If time[1] is ?, it should be the largest number that makes the hour valid.
3. For the minute component:
   • If either digit is ?, it can take the maximum possible valid value (5 for the tens place and 9 for the units place).

Code

public class LatestTimeByReplacingHiddenDigits {
    public String maximumTime(String time) {
        char[] t = time.toCharArray();
        
        // Handle hours part
        if (t[0] == '?') {
            t[0] = (t[1] == '?' || t[1] < '4') ? '2' : '1';
        }
        if (t[1] == '?') {
            t[1] = (t[0] == '2') ? '3' : '9';
        }
        
        // Handle minutes part
        if (t[3] == '?') {
            t[3] = '5';
        }
        if (t[4] == '?') {
            t[4] = '9';
        }
        
        return new String(t);
    }
    
    public static void main(String[] args) {
        LatestTimeByReplacingHiddenDigits solution = new LatestTimeByReplacingHiddenDigits();
        System.out.println(solution.maximumTime("2?:?0")); // output: "23:50"
        System.out.println(solution.maximumTime("0?:3?")); // output: "09:39"
        System.out.println(solution.maximumTime("1?:22")); // output: "19:22"
        System.out.println(solution.maximumTime("??:??")); // output: "23:59"
    }
}

Time Complexity

• The time complexity of this solution is O(1) because it involves a fixed number of operations regardless of the input.
• The space complexity is O(1) because we are using a constant amount of extra space for the character array transformation.

Each part (hours and minutes) is processed separately ensuring we maximize the digit at each position, leading to the latest valid time.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?