Given an array arr of 4 digits, find the latest 24-hour time that can be made using each digit exactly once.
24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.
Return the latest 24-hour time in "HH:MM" format.  If no valid time can be made, return an empty string.
 
Example 1:
Input: A = [1,2,3,4]
Output: "23:41"
Explanation: The valid 24-hour times are "12:34", "12:43", "13:24", "13:42", "14:23", "14:32", "21:34", "21:43", "23:14", and "23:41". Of these times, "23:41" is the latest.

Example 2:
Input: A = [5,5,5,5]
Output: ""
Explanation: There are no valid 24-hour times as "55:55" is not valid.

Example 3:
Input: A = [0,0,0,0]
Output: "00:00"

Example 4:
Input: A = [0,0,1,0]
Output: "10:00"

 
Constraints:

arr.length == 4
0 <= arr[i] <= 9

Difficulty: interview

Starter code:

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        

Solutions:
class Solution:
    def largestTimeFromDigits(self, A: List[int]) -> str:
        max_time = -1
        # enumerate all possibilities, with the permutation() func
        for h, i, j, k in itertools.permutations(A):
            hour = h*10 + i
            minute = j*10 + k
            if hour < 24 and minute < 60:
                max_time = max(max_time, hour * 60 + minute)
        
        if max_time == -1:
            return \"\"
        else:
            return \"{:02d}:{:02d}\".format(max_time // 60, max_time % 60)

class Solution:
    def largestTimeFromDigits(self, A: List[int]) -> str:

        def checkT(x):
            for n in range(x,-1,-1):
                if n in self.t:
                    self.ans += str(n)
                    self.t.remove(n)
                    return(True)
            return(False)

        for x in range(2,-1,-1):
            self.t = list(A)
            self.ans = \"\"
            if x == 2:
                if x in self.t:
                    self.ans += \"2\"
                    self.t.remove(2)
                    if checkT(3):
                        self.ans += \":\"
                        if checkT(5):
                            self.ans += str(self.t[0])
                            return(self.ans)
                continue

            if x in self.t:
                self.ans += str(x)
                self.t.remove(x)
                if checkT(9):
                    self.ans += \":\"
                    if checkT(5):
                        self.ans += str(self.t[0])
                        return(self.ans)
        return(\"\")


class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        
        perm = list(itertools.permutations(arr,4))
        output = []
        
        for a,b,c,d in perm:
            temp = \"{}{}:{}{}\".format(a,b,c,d)
            try:
                datetime.datetime.strptime(temp, \"%H:%M\")
            except:
                continue
                
            output.append(temp)
                
        if not output: return \"\"
        
        return max(output)

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        ptr1,ptr2,ptr3,ptr4=0,1,2,3
        time,maxtime = 0,0
        hour,mins = 0,0
        if arr == [0,0,0,0]:
            return \"00:00\"
        finalTime = \"\"
        valid = False
        for i in range(0,64):
            hour=arr[ptr1]*10+arr[ptr2]
            mins=arr[ptr3]*10+arr[ptr4]
            
            if(hour<24 and mins<60):
                time = hour*100+mins
                if(time>maxtime):
                    valid = True
                    maxtime = time
            if(ptr1>=3):ptr1 = 0 
            else: ptr1+=1
            if(ptr2>=3):ptr2 = 0 
            else: ptr2+=1
            if(ptr3>=3):ptr3 = 0 
            else: ptr3+=1
            if(ptr4>=3):ptr4 = 0 
            else: ptr4+=1
        ptr1,ptr2,ptr3,ptr4=3,2,0,1
        for i in range(0,64):
            hour=arr[ptr1]*10+arr[ptr2]
            mins=arr[ptr3]*10+arr[ptr4]
            if(hour<24 and mins<60):
                time = hour*100+mins
                if(time>maxtime):
                    valid = True
                    maxtime = time
            if(ptr1>=3):ptr1 = 0 
            else: ptr1+=1
            if(ptr2>=3):ptr2 = 0 
            else: ptr2+=1
            if(ptr3>=3):ptr3 = 0 
            else: ptr3+=1
            if(ptr4>=3):ptr4 = 0 
            else: ptr4+=1
        ptr1,ptr2,ptr3,ptr4=2,3,1,0
        for i in range(0,64):
            hour=arr[ptr1]*10+arr[ptr2]
            mins=arr[ptr3]*10+arr[ptr4]
            if(hour<24 and mins<60):
                time = hour*100+mins
                if(time>maxtime):
                    valid = True
                    maxtime = time
            if(ptr1>=3):ptr1 = 0 
            else: ptr1+=1
            if(ptr2>=3):ptr2 = 0 
            else: ptr2+=1
            if(ptr3>=3):ptr3 = 0 
            else: ptr3+=1
            if(ptr4>=3):ptr4 = 0 
            else: ptr4+=1
        ptr1,ptr2,ptr3,ptr4=2,0,3,1
        for i in range(0,64):
            hour=arr[ptr1]*10+arr[ptr2]
            mins=arr[ptr3]*10+arr[ptr4]
            if(hour<24 and mins<60):
                time = hour*100+mins
                if(time>maxtime):
                    valid = True
                    maxtime = time
            if(ptr1>=3):ptr1 = 0 
            else: ptr1+=1
            if(ptr2>=3):ptr2 = 0 
            else: ptr2+=1
            if(ptr3>=3):ptr3 = 0 
            else: ptr3+=1
            if(ptr4>=3):ptr4 = 0 
            else: ptr4+=1
        ptr1,ptr2,ptr3,ptr4=1,3,0,2
        for i in range(0,64):
            hour=arr[ptr1]*10+arr[ptr2]
            mins=arr[ptr3]*10+arr[ptr4]
            if(hour<24 and mins<60):
                time = hour*100+mins
                if(time>maxtime):
                    valid = True
                    maxtime = time
            if(ptr1>=3):ptr1 = 0 
            else: ptr1+=1
            if(ptr2>=3):ptr2 = 0 
            else: ptr2+=1
            if(ptr3>=3):ptr3 = 0 
            else: ptr3+=1
            if(ptr4>=3):ptr4 = 0 
            else: ptr4+=1
        ptr1,ptr2,ptr3,ptr4=1,0,3,2
        for i in range(0,64):
            hour=arr[ptr1]*10+arr[ptr2]
            mins=arr[ptr3]*10+arr[ptr4]
            if(hour<24 and mins<60):
                time = hour*100+mins
                if(time>maxtime):
                    valid = True
                    maxtime = time
            if(ptr1>=3):ptr1 = 0 
            else: ptr1+=1
            if(ptr2>=3):ptr2 = 0 
            else: ptr2+=1
            if(ptr3>=3):ptr3 = 0 
            else: ptr3+=1
            if(ptr4>=3):ptr4 = 0 
            else: ptr4+=1
        finalTimeStr = str(maxtime)
        print(finalTimeStr)
        if(len(finalTimeStr)==3):
            finalTimeStr = \"0\" + finalTimeStr
        return finalTimeStr[0]+finalTimeStr[1]+\":\"+finalTimeStr[2]+finalTimeStr[3] if valid else \"\"
    
    

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        
        count02 = 0
        count03 = 0
        count05 = 0
        count09 = 0
        newstr = \"\"
        for i in range(4):
            if arr[i]<=2:
                count02 += 1
            if arr[i]<=3:
                count03 += 1 
            if arr[i]<=5:
                count05 += 1
        if count02 == 0 or (2 in arr and count03 == 1) or (2 in arr and count02 == 1 and count05 <= 2) or count05 <= 1 :
            return \"\"
        if 2 in arr and count05 > 2:
            newstr = newstr + str(2)
            arr.remove(2)
        elif count05 <=2 or 2 not in arr:
            if 1 in arr:
                newstr = newstr + str(1)
                arr.remove(1)
            elif 0 in arr:
                newstr = newstr + str(0)
                arr.remove(0)
            else:
                return \"\"
        if newstr[0] != \"2\":
            for i in range(9, -1, -1):
                if i in arr:
                    newstr = newstr+ str(i) + \":\"
                    arr.remove(i)
                    break
        else:
            for i in range(3, -1, -1):
                if i in arr:
                    newstr = newstr+ str(i) + \":\"
                    arr.remove(i)
                    break
    
        for i in range(5, -1, -1):
            if i in arr:
                newstr = newstr+ str(i)
                arr.remove(i)
                break
        if len(newstr) <= 3:
            return \"\"
        newstr = newstr + str(arr[0])
            
        return newstr
    

class Solution:

    def largestTimeFromDigits(self, arr: List[int]) -> str:
        all_zero = True
        for item in arr:
            if item != 0:
                all_zero = False
        
        if all_zero:
            return \"00:00\"
        if min(arr) >= 3:
            return \"\"
        
        time = [0,0]
        

        def is_valid_hour(hour: int)->bool:
            return 0 <= hour and hour <= 23

        def is_valid_minute(minute: int)->bool:
            return 0 <= minute and minute <= 59

        def compare_and_update(time2: list)->None:
            if time2[0] > time[0]:
                time[0] = time2[0]
                time[1] = time2[1]
            elif time2[0] == time[0]:
                if time2[1] > time[1]:
                    time[1] = time2[1]
            else:
                pass

        for i in arr:
            sub1 = arr.copy()
            sub1.remove(i)
            for j in sub1:
                hr = i*10 + j
                if is_valid_hour(hr):
                    sub2 = sub1.copy()
                    sub2.remove(j)
                    mn1 = sub2[0]*10 + sub2[1]
                    mn2 = sub2[1]*10 + sub2[0]
                    if is_valid_minute(mn1):
                        new_time = [hr,mn1]
                        compare_and_update(new_time)
                    if is_valid_minute(mn2):
                        new_time = [hr,mn2]
                        compare_and_update(new_time)


        h2 = time[0] % 10 ; time[0] //= 10
        h1 = time[0]

        m2 = time[1] % 10 ; time[1] //= 10
        m1 = time[1]
        
        if h1 == h2 and h2 == m1 and m1 == m2 and m2 == 0:
            return \"\"

        return f\"{h1}{h2}:{m1}{m2}\"
        

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        ll = []
        def printAllKLength(set, k):
            n = len(set) 
            printAllKLengthRec(set, \"\", n, k)
        def printAllKLengthRec(set, prefix, n, k): 
            if (k == 0): 
                st = True
                for i in prefix:
                    if prefix.count(i) != set.count(i):
                        st = False
                        break
                if st == True and prefix not in ll:
                    ll.append(prefix)
                return prefix
            for i in range(n): 
                newPrefix = prefix + set[i] 
                printAllKLengthRec(set, newPrefix, n, k - 1) 
        set2=[]
        for i in arr:
            set2.append(str(i))
        k = 4
        printAllKLength(set2,k)
        ll.sort(reverse=True)
        s = ''
        for i in ll:
            if int(i[0])<2 and int(i[1])<10 and int(i[2]) <6 :
                s = i[0]+i[1]+\":\"+i[2]+i[3]
                break
            if int(i[0]) == 2 and int(i[1])<4 and int(i[2])<6:
                s = i[0] + i[1]+\":\"+i[2]+i[3]
                break
            else:
                continue
        return(s)
        
    
\t

        
                
            
        

                
                
            
            
            
            
            
                
        
        
        

class Solution:
    def check_valid_hour(self, arr:List[int], i: int, j: int) -> bool:
        minutes_index = [x for x in [0,1,2,3] if x != i and x != j]
        minutes = max(int(str(arr[minutes_index[0]])+str(arr[minutes_index[1]])), int(str(arr[minutes_index[1]])+str(arr[minutes_index[0]]))) 
        
        if minutes >= 60:
            minutes = min(int(str(arr[minutes_index[0]])+str(arr[minutes_index[1]])), int(str(arr[minutes_index[1]])+str(arr[minutes_index[0]])))             
        
        if minutes >= 60:
            return False
        return True
    
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        if len(arr) == 0:
            return \"\"
        
        index_i = -1
        index_j = -1
        max_hour = -1
        for i in range(len(arr)):
            for j in range(len(arr)):
                if i != j:
                    if int(str(arr[i])+str(arr[j])) < 24 and int(str(arr[i])+str(arr[j])) >= max_hour and self.check_valid_hour(arr,i,j):
                        max_hour = int(str(arr[i])+str(arr[j]))
                        index_i = i
                        index_j = j
        
        minutes_index = [x for x in [0,1,2,3] if x != index_i and x != index_j]
        
        if max_hour == -1:
            return \"\"
        elif max_hour == 0:
            max_hour = \"00\"
        if index_i == -1 and index_j == -1:
            minutes = \"00\"
        else:
            minutes = max(int(str(arr[minutes_index[0]])+str(arr[minutes_index[1]])), int(str(arr[minutes_index[1]])+str(arr[minutes_index[0]]))) 
        
        if minutes >= 60:
            minutes = min(int(str(arr[minutes_index[0]])+str(arr[minutes_index[1]])), int(str(arr[minutes_index[1]])+str(arr[minutes_index[0]])))             
        
        if minutes >= 60:
            return \"\"
        str_minutes = str(minutes)
        str_hours = str(max_hour)
        if len(str_minutes) == 1:
            str_minutes = \"0\" + str_minutes
        if len(str_hours) == 1:
            str_hours = \"0\" + str_hours
    
        return str_hours+\":\"+str_minutes
        
                
                
            
        
            
        

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        arr.sort()
        for hour in range(23, -1, -1):
            for minute in range(59, -1, -1):
                candidate = sorted([ hour // 10, hour % 10, minute // 10, minute % 10])
                if candidate == arr:
                    return \"%s%s:%s%s\" % (hour // 10, hour % 10, minute // 10, minute % 10)
        return \"\"



from itertools import permutations
    
class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        
        arr = sorted(arr, reverse=True)
        
        perms = permutations(arr)
        
        for perm in perms:
            m = perm[0] * 10 + perm[1]
            s = perm[2] * 10 + perm[3]
            
            if m < 24 and s < 60:
                strm = str(m)
                strs = str(s)
                if len(strm) < 2:
                    strm = \"0\" + strm
                if len(strs) < 2:
                    strs = \"0\" + strs
                return \"{}:{}\".format(strm, strs)
        
        return \"\"

#best way to solve this problem is by thinking how to solve this problem.
# get permutatation of all the number that can be formed with these sets.
# once you get the set, divide all the set with \":\"
# hour hand should be less than 24, and minutes hand be should be less than 60.
# get all the permutation with that no, and store them in list , and run a compare algorithm, or sort algorithm

import itertools
class Solution:
    def largestTimeFromDigits(self, inputlist):
        allthevalues = list(itertools.permutations(inputlist, 4))
        filteredhourvalue = list(filter(lambda x : x[0]*10 + x[1] < 24 ,allthevalues ))
        filteredminvalue = list(filter(lambda x : x[2]*10 + x[3] < 60 ,filteredhourvalue ))
        if len(filteredminvalue) == 0:
            return \"\"
        else:
            actualtime = list(max(filteredminvalue))
            return \"{}{}:{}{}\".format(*actualtime)






class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        import itertools
        ret = ''
        for a, b, c, d in itertools.permutations(arr):
            h = a*10 + b
            m = c*10 + b
            if h >= 24 or m >59:
                continue
                
            t = f\"{a}{b}:{c}{d}\"
            if not ret:
                ret = t
            else:
                ret = max(ret, t)
        return ret            
                

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        m1 = -1
        m = 0
        MA = 1
        dict = {-1:0}
        for i in range(0,4):
            for j in range(i+1,4):
                if i != j:
                    arr2 = deepcopy(arr)
                    del arr2[j]
                    del arr2[i]
                    a1 = arr2[0]+10*arr2[1]
                    a2 = arr2[1]+10*arr2[0]
                    if 1>0:
                        if a1>= 60 and a2 >= 60:
                            MA = -1
                        elif a1 < 60 and a2 <60:
                            m = max(a1,a2)
                            MA = 1
                        elif a1 < 60:
                            m = a1
                            MA = 1
                        elif a2 <60:
                            m = a2
                            MA = 1
                    if MA ==1:
                        if (10*arr[i] + arr[j]) <24 and (10*arr[j] + arr[i]) <24:
                            if max(10*arr[i]+arr[j],10*arr[j]+arr[i])>m1:
                                m1 = max(10*arr[i]+arr[j],10*arr[j]+arr[i])
                                dict[m1]=m
                            elif max(10*arr[i]+arr[j],10*arr[j]+arr[i]) == m1:
                                if dict[m1]< m:
                                    dict [m1]=m
                        elif (10*arr[i]+arr[j])<24:
                            if (10*arr[i]+arr[j])>m1:
                                m1 = (10*arr[i]+arr[j])
                                dict[m1]=m
                            elif (10*arr[i]+arr[j]) == m1:
                                if dict[m1]< m:
                                    dict[m1]=m
                        elif (10*arr[j] + arr[i])<24:
                            if (10*arr[j] + arr[i])>m1:
                                m1 = 10*arr[j] + arr[i]
                                dict[m1]=m
                            elif (10*arr[j] + arr[i]) == m1:
                                 if dict[m1]< m:
                                    dict [m1]=m
        if m1 == -1:
            return ''
        else:
            if m1//10==0 and dict[m1]//10==0:
                return '0'+ str(m1) +':0'+ str(dict[m1]) 
            elif m1//10==0:
                return '0'+str(m1) +':'+ str(dict[m1])
            elif dict[m1]//10==0:
                return str(m1) +':0'+ str(dict[m1])
            else:
                return str(m1) +':'+ str(dict[m1])


class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        out = \"\"
        for P in itertools.permutations(arr):
            if P[0]*10 + P[1] <= 23 and P[2] <= 5:
                out = max(out, str(P[0])+str(P[1]) + \":\" + str(P[2])+str(P[3]))
        
        return out
        
        
        
        
            

class Solution:
    def largestTimeFromDigits(self, A: List[int]) -> str:

        max_time = -1

        def build_time(permutation):
            nonlocal max_time

            h, i, j, k = permutation
            hour = h*10 + i
            minute = j*10 + k
            if hour < 24 and minute < 60:
                max_time = max(max_time, hour * 60 + minute)

        def swap(array, i, j):
            if i != j:
                array[i], array[j] = array[j], array[i]

        def permutate(array, start):
            if start == len(array):
                build_time(array)
                return

            for index in range(start, len(array)):
                swap(array, index, start)
                # repeat the permutation with the original array mutated
                permutate(array, start+1)
                swap(array, index, start)

        permutate(A, 0)
        if max_time == -1:
            return \"\"
        else:
            return \"{:02d}:{:02d}\".format(max_time // 60, max_time % 60)

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        def isValid(time):
            return (10 * time[0] + time[1] < 24) and (10 * time[2] + time[3] < 60)
        def perms(items):
            res = []
            if items == []:
                return [[]]
            for i in range(len(items)):
                #print(items, i, items[:i] + items[i+1::])
                res = res + [[items[i]] + rest_of_perm for rest_of_perm in perms(items[:i] + items[i+1::])]
            return res
        #print(perms(arr))
        validTimes = [t for t in perms(arr) if isValid(t)]
        if validTimes == []:
            return \"\"
        maxTime = max(validTimes)
        #print(maxTime)
        res = \"\".join([str(x) for x in maxTime])
        return res[:2] + \":\" + res[2::]