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"