Maximum Time Combination

Given 4 digits, find the maximum valid time that can be displayed on a digital clock (in 24-hour format) using those digits. For example, given digits 1,8,3,2, the maximum valid time is "23:18". Note that "28:31" is not a valid time.

Write a function: that, given 4 digits A,B,C,D, returns the maximum valid time in string format "HH:MM" or "NOT POSSIBLE" if it is not possible to display a valid time.

For example,

given 1,8,3,2, the function should return "23:18"
Given 2,4,0,0, the function should return "20:40"
Given 3,0,7,0, the function should return "07:30"
Given 9,1,9,7, the function should return "NOT POSSIBLE"

Assume that:

• A, B, C, and D are integers within the range [0..9].

• In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

The Idea: Just count down from that maximum time (23:59) and check that all the digits if [a,b,c,d] are contained within this time.

Complexity: O(60*24) time and O(1) space

from datetime import *
from collections import Counter

def max_time_combination(a, b, c, d):
    digits = Counter([str(i) for i in [a,b,c,d]] + [':'])
    next_time = datetime.strptime("23:59", "%H:%M")
    min_time = datetime.strptime("00:00", "%H:%M")

    while next_time >= min_time:
        # while use a multiset (counter) to confirm anagrams
        extract = next_time.strftime("%H:%M")
        if Counter(extract) == digits:
            return str(extract)
        next_time = next_time - timedelta(minutes=1)
    return "NOT POSSIBLE"


print(max_time_combination(1,8,3,2)) # "23:18"
print(max_time_combination(2,4,0,0)) # "20:40"
print(max_time_combination(3,0,7,0)) # "07:30"
print(max_time_combination(9,1,9,7)) # "NOT POSSIBLE"