# Leetcode: Next Closest Time

Next Closest Time

Similar Problems:

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.
```

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/next-closest-time
## Basic Ideas: Only pow(4, 4) combinations
##      Get all of them, and rule out the invalid onces
##      Convert the time string to seconds
##      Compare the absolute diff with rotated enforced
##
## Assumption: "11:11" -> "11:11"
## Complexity: Time O(1), Space O(1)
class Solution:
def nextClosestTime(self, time):
"""
:type time: str
:rtype: str
"""
import sys
ch_set = set(time)
ch_set.remove(':')
if len(ch_set) == 1: return time

l = [""]
for i in range(4):
l2 = []
for ch in ch_set:
for item in l:
if i == 1:
l2.append("%s%s:" % (item, ch))
else:
l2.append("%s%s" % (item, ch))
l = l2

minutes = self.getMinutes(time)
min_diff, index  = sys.maxsize, None
total_minutes = 24*60
for i in range(len(l)):
t = l[i]
# check whether t is valid
if int(t[0])*10+int(t[1]) >= 24: continue
if int(t[3])*10+int(t[4]) >= 60: continue

diff = (self.getMinutes(t)-minutes+total_minutes) % total_minutes
if diff == 0: continue

if min_diff > diff:
min_diff, index = diff, i

return l[index]

def getMinutes(self, time):
return (int(time[0])*10 + int(time[1]))*60+(int(time[3])*10 + int(time[4]))
```

Original URL: https://code.dennyzhang.com/next-closest-time

Connect with Denny In LinkedIn Or Slack

Share It, If You Like It.