681 Next Closest Time

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.

The Idea: Add 1 minute at a time until you find a time where all the digits of the next time is within the digits of the original time. Because time wraps about itself, we are guareenteed to obtain an answer within 24*60 time steps (60 minutes, for 24 hours), all the time. Lets strp and strf time take care of all the trival arithmetics for us.

Complexity: O(1) time and space

from datetime import *

class Solution:
    def nextClosestTime(self, time):
        """
        :type time: str
        :rtype: str
        """

        digits = set(time)
        next_time = datetime.strptime(time, "%H:%M")
        while True:
            next_time = next_time + timedelta(minutes=1)
            extract = next_time.strftime("%H:%M")
            if self.within(digits, set(extract)):
                return extract

    def within(self, seta, setb):
        for i in setb:
            if i not in seta:
                return False
        return True