algoadvance

Leetcode 3114. Latest Time You Can Obtain After Replacing Characters

Problem Statement

You are given a string time in the form of “HH:MM”. Some of the digits are hidden (represented by ?). The valid times are between 00:00 and 23:59. Replace the ? characters with digits (0-9) in such a way that the time represented by the string is the latest valid time possible.

Clarifying Questions

  1. Is there guaranteed to be at least one ? in the time string?
  2. Are we always working with 24-hour format time?
  3. What should the output be? The fully constructed latest time?

Code

public class LatestTime {
    public static String getLatestTime(String time) {
        char[] timeChars = time.toCharArray();
        
        // Handle H1 position
        if (timeChars[0] == '?') {
            if (timeChars[1] == '?' || timeChars[1] <= '3') {
                timeChars[0] = '2';
            } else {
                timeChars[0] = '1';
            }
        }
        
        // Handle H2 position
        if (timeChars[1] == '?') {
            if (timeChars[0] == '2') {
                timeChars[1] = '3';
            } else {
                timeChars[1] = '9';
            }
        }
        
        // Handle M1 position
        if (timeChars[3] == '?') {
            timeChars[3] = '5';
        }
        
        // Handle M2 position
        if (timeChars[4] == '?') {
            timeChars[4] = '9';
        }
        
        return new String(timeChars);
    }

    public static void main(String[] args) {
        // Test cases
        System.out.println(getLatestTime("2?:?0")); // Expected "23:50"
        System.out.println(getLatestTime("0?:3?")); // Expected "09:39"
        System.out.println(getLatestTime("1?:22")); // Expected "19:22"
        System.out.println(getLatestTime("?4:5?")); // Expected "14:59"
    }
}

Strategy

  1. First character (‘H1’) handling:
    • If timeChars[0] is ‘?’, check the next character timeChars[1].
    • If timeChars[1] is ‘?’ or it is between ‘0’ and ‘3’, set timeChars[0] to ‘2’.
    • Otherwise, set timeChars[0] to ‘1’.
  2. Second character (‘H2’) handling:
    • If timeChars[1] is ‘?’, check the first character timeChars[0].
    • If timeChars[0] is ‘2’, set timeChars[1] to ‘3’ to ensure the highest valid hour (23).
    • Otherwise, set timeChars[1] to ‘9’.
  3. Third character (‘M1’) handling:
    • If timeChars[3] is ‘?’, set it to ‘5’ because the highest valid minute tens is 5.
  4. Fourth character (‘M2’) handling:
    • If timeChars[4] is ‘?’, set it to ‘9’ because the highest valid minute ones is 9.

This strategy ensures we replace the ‘?’ characters with digits to get the latest possible time.

Time Complexity

The time complexity of this algorithm is O(1) because the operations are constant time checks and replacements based on fixed conditions. The space complexity is also O(1) as no extra space proportional to input size is used.

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