Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused. You may assume the given input string is always valid. For example, "01:34", "12:09" are valid. "1:34", "12:9" are invalid.

Example

Example 1:
Input: "19:34"
Output: "19:39"
Explanation:
  The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.  
  It is not 19:33, because this occurs 23 hours and 59 minutes later.
Example 2:
Input: "23:59"
Output: "22:22"
Explanation: It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.

public class Solution {
    /**
     * @param time: the given time
     * @return: the next closest time
     */
    public String nextClosestTime(String time) {
        int[] digits = new int[4];
        digits[0] = Integer.parseInt(time.substring(0, 1));
        digits[1] = Integer.parseInt(time.substring(1, 2));
        digits[2] = Integer.parseInt(time.substring(3, 4));
        digits[3] = Integer.parseInt(time.substring(4, 5));

        //get all possible permuatation of the digits as another time
        List<List<Integer>> times = new ArrayList<>();
        List<Integer> atime = new ArrayList<>();
        findTimes(digits, times, atime);

        int minutes = (digits[0] * 10 + digits[1]) * 60 + (digits[2] * 10 + digits[3]);
        int diff = Integer.MAX_VALUE;
        int targetIndex = 0;
        int newMinutes = 0;
        for(int i = 0; i < times.size(); i++) {
            if((times.get(i).get(0) * 10 + times.get(i).get(1)) > 23 || (times.get(i).get(2) * 10 + times.get(i).get(3)) > 59) continue;
            newMinutes = (times.get(i).get(0) * 10 + times.get(i).get(1)) * 60 + (times.get(i).get(2) * 10 + times.get(i).get(3));
            if(newMinutes <= minutes) newMinutes += (24 * 60);
            if((newMinutes - minutes) < diff) {
                diff = newMinutes - minutes;
                targetIndex = i;
            }
        }
        return ("" + times.get(targetIndex).get(0) + times.get(targetIndex).get(1) + ":" + times.get(targetIndex).get(2) + times.get(targetIndex).get(3));

    }

    private void findTimes(int[] digits, List<List<Integer>> times, List<Integer> atime) {
        if(atime.size() == 4) {
            times.add(new ArrayList(atime));
            return;
        }

        for(int i = 0; i < 4; i++) {
            atime.add(digits[i]);
            findTimes(digits, times, atime);
            atime.remove(atime.size() - 1);
        }
    }
}