681. Next Closest Time

1class Solution {
2    private int originalTotalMinutes;
3    private int minDifference;
4    private String answer;
5    private Set<Character> validDigits;
6
7    // This method finds the next closest time using the digits of the given time.
8    public String nextClosestTime(String time) {
9        // Convert the given time to total minutes.
10        originalTotalMinutes = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3));
11        // Initialize the minimum difference to a large value.
12        minDifference = Integer.MAX_VALUE;
13        // Create a set to store the unique digits from the time.
14        validDigits = new HashSet<>();
15        // Tracks the minimum digit.
16        char minDigit = '9';
17        for (char c : time.toCharArray()) {
18            if (c != ':') {
19                validDigits.add(c);
20                if (c < minDigit) {
21                    minDigit = c;
22                }
23            }
24        }
25        answer = null;
26        // Begin deep first search to build valid times.
27        deepFirstSearch("");
28        // If no answer was found in the search, use the smallest digit four times to create the earliest possible time.
29        if (answer == null) {
30            answer = "" + minDigit + minDigit + ":" + minDigit + minDigit;
31        }
32        return answer;
33    }
34
35    // Helper method to perform deep first search over the possible times.
36    private void deepFirstSearch(String current) {
37        // When the current string is 4 digits long, we have a complete time.
38        if (current.length() == 4) {
39            if (!isValidTime(current)) {
40                return;
41            }
42            int potentialTimeMinutes
43                = Integer.parseInt(current.substring(0, 2)) * 60 + Integer.parseInt(current.substring(2));
44            // Check if the potential time is closer to the original time.
45            if (potentialTimeMinutes > originalTotalMinutes && potentialTimeMinutes - originalTotalMinutes < minDifference) {
46                minDifference = potentialTimeMinutes - originalTotalMinutes;
47                answer = current.substring(0, 2) + ":" + current.substring(2);
48            }
49            return;
50        }
51        // Recurse for each valid digit to build the time string.
52        for (char c : validDigits) {
53            deepFirstSearch(current + c);
54        }
55    }
56
57    // Helper method to check if a string represents a valid time.
58    private boolean isValidTime(String timeStr) {
59        int hour = Integer.parseInt(timeStr.substring(0, 2));
60        int minute = Integer.parseInt(timeStr.substring(2));
61        return 0 <= hour && hour < 24 && 0 <= minute && minute < 60;
62    }
63}
64

1#include <string>
2#include <set>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8private:
9    int originalTotalMinutes;
10    int minDifference;
11    string answer;
12    set<char> validDigits;
13
14    // Helper method to check if a string represents a valid time.
15    bool isValidTime(const string& timeStr) {
16        int hour = stoi(timeStr.substr(0, 2));
17        int minute = stoi(timeStr.substr(2));
18        return hour >= 0 && hour < 24 && minute >= 0 && minute < 60;
19    }
20
21    // Helper method to perform depth first search over the possible times.
22    void depthFirstSearch(const string& current) {
23        // When the current string is 4 digits long, a complete time is formed.
24        if (current.length() == 4) {
25            if (!isValidTime(current)) {
26                return;
27            }
28            int potentialTimeMinutes = stoi(current.substr(0, 2)) * 60 + stoi(current.substr(2));
29            // Check if the potential time is closer to the original time.
30            if (potentialTimeMinutes > originalTotalMinutes &&
31                potentialTimeMinutes - originalTotalMinutes < minDifference) {
32                minDifference = potentialTimeMinutes - originalTotalMinutes;
33                answer = current.substr(0, 2) + ":" + current.substr(2);
34            }
35            return;
36        }
37        // Recurse for each valid digit to build the time string.
38        for (char c : validDigits) {
39            depthFirstSearch(current + c);
40        }
41    }
42
43public:
44    // This method finds the next closest time using the digits of the given time.
45    string nextClosestTime(string time) {
46        // Convert the given time to total minutes.
47        originalTotalMinutes = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3));
48        // Initialize the minimum difference to a large value.
49        minDifference = INT_MAX;
50        char minDigit = '9';
51        // Create a set to store the unique digits from the time.
52        for (char c : time) {
53            if (c != ':') {
54                validDigits.insert(c);
55                if (c < minDigit) {
56                    minDigit = c;
57                }
58            }
59        }
60        answer = "";
61        // Begin depth first search to build valid times.
62        depthFirstSearch("");
63        // If no answer was found in the search, use the smallest digit four times to create the earliest possible time.
64        if (answer.empty()) {
65            answer = string(2, minDigit) + ":" + string(2, minDigit);
66        }
67        return answer;
68    }
69};
70

1// Declare global variables
2let originalTotalMinutes: number;
3let minDifference: number;
4let answer: string;
5let validDigits: Set<string>;
6
7// Converts the input time to total minutes since midnight
8function convertToMinutes(time: string): number {
9    const hours = parseInt(time.substring(0, 2), 10);
10    const minutes = parseInt(time.substring(3), 10);
11    return hours * 60 + minutes;
12}
13
14// Determines if a given time string represents a valid time
15function isValidTime(timeStr: string): boolean {
16    const hour = parseInt(timeStr.substring(0, 2), 10);
17    const minute = parseInt(timeStr.substring(2), 10);
18    return hour >= 0 && hour < 24 && minute >= 0 && minute < 60;
19}
20
21// Performs deep first search over the possible times
22function deepFirstSearch(current: string): void {
23    // When the current string is 4 digits long, a complete time is formed
24    if (current.length === 4) {
25        if (!isValidTime(current)) {
26            return;
27        }
28
29        const potentialTotalMinutes = convertToMinutes(current.substring(0, 2) + ':' + current.substring(2));
30      
31        // Check if the potential time is closer to the original time but only if it's later
32        if (potentialTotalMinutes > originalTotalMinutes && potentialTotalMinutes - originalTotalMinutes < minDifference) {
33            minDifference = potentialTotalMinutes - originalTotalMinutes;
34            answer = current.substring(0, 2) + ':' + current.substring(2);
35        }
36        return;
37    }
38
39    // Recursively append valid digits to build the time string
40    validDigits.forEach((digit: string) => {
41        deepFirstSearch(current + digit);
42    });
43}
44
45// This method finds the next closest time using the digits of the given time
46function nextClosestTime(time: string): string {
47    originalTotalMinutes = convertToMinutes(time);
48
49    minDifference = Number.MAX_SAFE_INTEGER;
50    validDigits = new Set<string>();
51
52    // Find the minimum digit for use in case no valid time is found
53    let minDigit: string = '9';
54    for (const c of time) {
55        if (c !== ':') {
56            validDigits.add(c);
57            minDigit = c < minDigit ? c : minDigit;
58        }
59    }
60
61    answer = null;
62
63    // Begin deep first search to build valid times
64    deepFirstSearch('');
65
66    // If no valid time was found, create the earliest possible time using the smallest digit
67    if (answer === null) {
68        answer = minDigit + minDigit + ':' + minDigit + minDigit;
69    }
70
71    return answer;
72}
73
74// Example usage:
75// const closestTime = nextClosestTime('19:34');
76// console.log(closestTime); // Outputs the next closest time using the same digits
77