Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/681.html

681. Next Closest Time

Level

Medium

Description

Given a time represented in the format “HH:MM”, form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, “01:34”, “12:09” are all valid. “1:34”, “12:9” are all invalid.

Example 1:

Input: “19:34”

Output: “19:39”

Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later. It is not 19:33, because this occurs 23 hours and 59 minutes later.

Example 2:

Input: “23:59”

Output: “22:22”

Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day’s time since it is smaller than the input time numerically.

Solution

Simulate all possible times minute by minute. If a time can be formed by reusing the current digit, return the time.

When returning the time, use String.format to convert it into the required format “HH:MM”.

  • class Solution {
        public String nextClosestTime(String time) {
            String hourStr = time.substring(0, 2), minuteStr = time.substring(3);
            Set<Integer> set = new HashSet<Integer>();
            for (int i = 0; i < 2; i++) {
                set.add(hourStr.charAt(i) - '0');
                set.add(minuteStr.charAt(i) - '0');
            }
            int[] timeArray = {Integer.parseInt(hourStr), Integer.parseInt(minuteStr)};
            for (int i = 1; i <= 1440; i++) {
                next(timeArray);
                if (isReuse(timeArray, set)) {
                    String nextTime = String.format("%02d:%02d", timeArray[0], timeArray[1]);
                    return nextTime;
                }
            }
            return time;
        }
    
        public void next(int[] timeArray) {
            timeArray[1]++;
            if (timeArray[1] >= 60) {
                timeArray[1] %= 60;
                timeArray[0]++;
            }
            if (timeArray[0] >= 24)
                timeArray[0] %= 24;
        }
    
        public boolean isReuse(int[] timeArray, Set<Integer> set) {
            int hour = timeArray[0], minute = timeArray[1];
            if (!set.contains(hour / 10))
                return false;
            else if (!set.contains(hour % 10))
                return false;
            else if (!set.contains(minute / 10))
                return false;
            else if (!set.contains(minute % 10))
                return false;
            else
                return true;
        }
    }
    
  • class Solution:
        def nextClosestTime(self, time: str) -> str:
            def check(t):
                h, m = int(t[:2]), int(t[2:])
                return 0 <= h < 24 and 0 <= m < 60
    
            def dfs(curr):
                if len(curr) == 4:
                    if not check(curr):
                        return
                    nonlocal ans, d
                    p = int(curr[:2]) * 60 + int(curr[2:])
                    if t < p < t + d:
                        d = p - t
                        ans = curr[:2] + ':' + curr[2:]
                    return
                for c in s:
                    dfs(curr + c)
    
            s = {c for c in time if c != ':'}
            t = int(time[:2]) * 60 + int(time[3:])
            d = inf
            ans = None
            dfs('')
            if ans is None:
                mi = min(int(c) for c in s)
                ans = f'{mi}{mi}:{mi}{mi}'
            return ans
    
    
    

All Problems

All Solutions