Largest Time for Given Digits

 Given an array of 4 digits, return the largest 24 hour time that can be made.

The smallest 24 hour time is 00:00, and the largest is 23:59.  Starting from 00:00, a time is larger if more time has elapsed since midnight.

Return the answer as a string of length 5.  If no valid time can be made, return an empty string.

 

Example 1:

Input: [1,2,3,4]
Output: "23:41"

Example 2:

Input: [5,5,5,5]
Output: ""

 

Note:

1. A.length == 4
2. 0 <= A[i] <= 9

My Answer:

Basic Logic: since number of input array is fixed, 4, number of all 4 digits combination is fixed as well, 4*3*2. We can sort all the combinations first in descending order, and then find the 1st valid combination

class Solution {
    public String largestTimeFromDigits(int[] A) {
        
        if (A == null || A.length != 4) {
            return "";
        }
        Arrays.sort(A);
        if (A[0] < 0 || A[0] > 2 || (A[0] == 2 && A[1] > 3) || (A[0] == 2 && A[1] <= 3 && A[2] >=6)) {
            return "";
        }
        List<ArrayList<String>> results = new ArrayList<ArrayList<String>>();
        List<String> allResults = getAllCombinations(A, 0).stream().map(s -> {
            StringBuilder sb = new StringBuilder(s);
            sb.insert(2, ":");
            return sb.toString();
        }).collect(Collectors.toList());
        Collections.sort(allResults, Collections.reverseOrder());
        for (String result : allResults) {
            if (isResultValid(result)) {
                return result;
            }
        }
        return "";
    }
    
    private boolean isResultValid(String result) {
        if (Integer.valueOf(result.substring(0,2)) >= 24 || Integer.valueOf(result.substring(3,5)) > 59) {
            return false;
        }
            return true;
    }
    
    private List<String> getAllCombinations(int A[], int index) {
        
        if (index >= A.length ) {
            return new ArrayList<String>(){
                {
                    add("");
                }
            };
        }
        List<String> currentResults = new ArrayList<String>();
        List<String> nextResults = getAllCombinations(A, index + 1);
        for (String nextResult : nextResults) {
            for (int i = 0; i <= nextResult.length(); i ++) {
                StringBuilder sb = new StringBuilder(nextResult);
                sb.insert(i, String.valueOf(A[index]));
                currentResults.add(sb.toString());
            }
        }
        return currentResults;
    }
}