681. Next Closest Time

class Solution {
    public String nextClosestTime(String time) {
        List<Integer> list = new ArrayList<>();
        int[] f = new int[10];
        for(char ch : time.toCharArray())
            if(ch != ':') f[ch - '0']++;  // collect all characters
        for(int i = 0; i < 10; i++) if(f[i] > 0) list.add(i);
        dfs(list, new char[4], 0);
        // now loop through genTimes
        // System.out.println(genTimes);
        int inf = Integer.MAX_VALUE, diff = inf;
        String res = "";
        for(String times : genTimes)
        {
            if(!isvalid(times)) continue;
            int timeDifference = timeDiff(time, times);
            if(timeDifference < diff)
            {
                diff = timeDifference;
                res = times;
            }
        }
        return res.substring(0, 2) + ":" + res.substring(2);
    }

    int timeDiff(String str1, String str2)
    {
        int h1 = Integer.valueOf(str1.substring(0, 2)), m1 = Integer.valueOf(str1.substring(3)),
            h2 = Integer.valueOf(str2.substring(0, 2)), m2 = Integer.valueOf(str2.substring(2));
        int time1 = h1 * 60 + m1, time2 = h2 * 60 + m2;
        if(time1 < time2) return time2 - time1;
        else return time2 + 24 * 60 - time1;
    }

    boolean isvalid(String str)
    {
        int hour = Integer.valueOf(str.substring(0, 2)), min = Integer.valueOf(str.substring(2));
        if(hour > 23 || min > 59) return false;
        return true;
    }

    List<String> genTimes = new ArrayList<>();

    void dfs(List<Integer> list, char[] chs, int pos)
    {
        if(pos == 4)
        {
            String str = String.valueOf(chs);
            if(isvalid(str)) genTimes.add(str);
            return;
        }
        for(int k : list)
        {
            chs[pos] = (char)('0' + k);
            dfs(list, chs, pos + 1);
        }
    }
}