Welcome to Subscribe On Youtube

681. Next Closest Time

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: time = "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: time = "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.

 

Constraints:

• time.length == 5
• time is a valid time in the form "HH:MM".
• 0 <= HH < 24
• 0 <= MM < 60

Solutions

• Java
• Python

• class Solution {
      private int t;
      private int d;
      private String ans;
      private Set<Character> s;
  
      public String nextClosestTime(String time) {
          t = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3));
          d = Integer.MAX_VALUE;
          s = new HashSet<>();
          char mi = 'z';
          for (char c : time.toCharArray()) {
              if (c != ':') {
                  s.add(c);
                  if (c < mi) {
                      mi = c;
                  }
              }
          }
          ans = null;
          dfs("");
          if (ans == null) {
              ans = "" + mi + mi + ":" + mi + mi;
          }
          return ans;
      }
  
      private void dfs(String curr) {
          if (curr.length() == 4) {
              if (!check(curr)) {
                  return;
              }
              int p
                  = Integer.parseInt(curr.substring(0, 2)) * 60 + Integer.parseInt(curr.substring(2));
              if (p > t && p - t < d) {
                  d = p - t;
                  ans = curr.substring(0, 2) + ":" + curr.substring(2);
              }
              return;
          }
          for (char c : s) {
              dfs(curr + c);
          }
      }
  
      private boolean check(String t) {
          int h = Integer.parseInt(t.substring(0, 2));
          int m = Integer.parseInt(t.substring(2));
          return 0 <= h && h < 24 && 0 <= m && m < 60;
      }
  }
  

• 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