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.

&nbsp;
Example 1:

Input: arr = [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: arr = [5,5,5,5]
Output: ""
Explanation: There are no valid 24-hour times as "55:55" is not valid.


&nbsp;
Constraints:


	arr.length == 4
	0 &lt;= arr[i] &lt;= 9


class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        res = ""
        digit_freq = collections.Counter(arr)
        # first digit
        
        
        if 2 in arr and sum([digit_freq[d] for d in range(6)]) > 2:
            res += "2"
            arr.remove(2)
        else:
            for digit in [1,0]:
                if digit in arr:
                    res += str(digit)
                    arr.remove(digit)
                    break
        # can't make 24-hour time
        if len(res) == 0:
            return ""
        
        # second digit 0-3
        if res == "2":
            for digit in [3,2,1,0]:
                if digit in arr:
                    res += str(digit)
                    arr.remove(digit)
                    break
            # no 0-3 left in arr
            if len(res) == 1:
                return ""
        # second digit 0-9
        else:
            for digit in range(9,-1,-1):
                if digit in arr:
                    res += str(digit)
                    arr.remove(digit)
                    break
        
        res += ":"
        
        for digit in range(5, -1, -1):
            if digit in arr:
                res += str(digit)
                arr.remove(digit)
                break
            
        if len(res) == 3:
            return ""
        
        for digit in range(9,-1,-1):
            if digit in arr:
                res += str(digit)
                return res
                
class Solution {
    public String largestTimeFromDigits(int[] arr) {
        int[] count = new int[10];
        for (int num: arr) {
            count[num]++;
        }
        StringBuilder sb = backTrack(count, new StringBuilder());
        if (sb.length() == 4) sb.insert(2, ':');
        return sb.toString();
        
    }
    private StringBuilder backTrack(int[] count, StringBuilder sb) {
        int size = sb.length();
        int start = 0;
        if (size == 0) {
            start = 2;
        }
        if (size == 1) {
            start = sb.charAt(0) == '2' ? 3 : 9;
        }
        if (size == 2) {
            start = 5;
        }
        if (size == 3) {
            start = 9;
        }
        for (int i = start; i >= 0; i--) {
            if (count[i] == 0) continue;
            count[i]--;
            sb.append(i);
            backTrack(count, sb);
            if (sb.length() == 4) {
                return sb;
            }
            else {
                count[Character.getNumericValue(sb.charAt(sb.length() - 1))]++;
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        return sb;
    }
}
class Solution {
public:
    string largestTimeFromDigits(vector<int>& arr) {
        sort(arr.rbegin(), arr.rend());
        used.resize(4);
        
        string ret = "";
        if(!dfs(arr,0,0)) return ret;
        else
        {
            for(int i=0;i<2;i++)
                ret.push_back(ans[i] + '0');
            
            ret.push_back(':');
            
            for(int i=2;i<4;i++)
                ret.push_back(ans[i] + '0');
        }
        return ret;
    }
    
private:
    vector<int> min = {600, 60, 10, 1};
    vector<int> ans;
    vector<int> used;
    bool dfs(const vector<int>& arr, int totalhour,int totalmin)
    {
        if(totalhour >= 24 * 60) return false;
        if(totalmin >= 60) return false;
        if(ans.size() == 4) return true;
        
        for(int i=0;i<4;i++)
        {
            if(used[i]) continue;
            used[i] = 1;
            
            int pos = ans.size();
            if(pos<2) totalhour += arr[i] * min[pos];
            else totalmin += arr[i] * min[pos];
            
            ans.push_back(arr[i]);
            
            if(dfs(arr,totalhour,totalmin)) return true;
            
            if(pos<2) totalhour -= arr[i] * min[pos];
            else totalmin -= arr[i] * min[pos];
            
            ans.pop_back();
            used[i] = 0;
        }
        
        return false;
    }
};
var largestTimeFromDigits = function(arr) {
    let max=-1;
    for(let A=0; A<4; A++){
        for(let B=0; B<4; B++){
			if(B==A){continue};
            for(let C=0; C<4; C++){
				if(C==A||C==B||arr[C]>=6){continue};
                for(let D=0; D<4; D++){
					if(D==A||D==B||D==C){continue};
                    let time=arr[A]*1000+arr[B]*100+arr[C]*10+arr[D];
                    if(time<2400){max=Math.max(max, time));
                }
            }
        }
    }
	// Case1: max<0, which means NOTHING VALID -> return ""
	// Case2: max isn't 4 digits. i.e.[0,0,0,0] -> padStart to make "0000"
    let output=max.toString().padStart(4,0);
    return max<0? "": output.substr(0,2)+":"+output.substr(2);
};
Largest Time for Given Digits