681. Next Closest Time

T: O(nlogn), n is (9*9*9*9) I use dfs to enumerate all possible time, then filter only correct time format...and find the one is matching our input, and find the next one that is the ans.

```java
class Solution {
    public String nextClosestTime(String time) {        
        char[] input = new char[]{time.charAt(0), time.charAt(1), time.charAt(3), time.charAt(4)};

        List<String> allTimes = new ArrayList<>();
        dfs(input, new StringBuilder(), allTimes);
        Collections.sort(allTimes);

        List<String> validTimes = new ArrayList<>();
        for (int i = 0; i < allTimes.size(); i++) {
            if (!isValidTime(allTimes.get(i))) {
                continue;
            }
            validTimes.add(allTimes.get(i));
        }

        String rs = "";
        for (int i = 0; i < validTimes.size(); i++) {
            if (validTimes.get(i).equals(time.replace(":", ""))) {
                rs = (i == validTimes.size() - 1 ? validTimes.get(0) : validTimes.get(i+1));
            }
        }
        return rs.charAt(0) + "" + rs.charAt(1) + ":" + rs.charAt(2)+ "" +rs.charAt(3);
    }
    private void dfs(char[] input, StringBuilder sb, List<String> result) {
        if (input.length == sb.length()) {
            result.add(new String(sb.toString()));
            return;
        }
        for (int i = 0; i < input.length; i++) {
            sb.append(input[i]);
            dfs(input, sb, result);
            sb.deleteCharAt(sb.length()-1);
        }
    }

    private boolean isValidTime(String t) {
        int first = (t.charAt(0) - '0');
        int second = (t.charAt(1) - '0');
        int third = (t.charAt(2) - '0');
        if (first == 2) {
            if (second >= 4) {
                return false;
            }
        }
        if (first >= 3) {
            return false;
        }
        if (third >= 6) {
            return false;
        }
        return true;
    }
}

/***

S1: DFS to gen all valid time, then sort it asc
find the current time, and return next one (if it's the last one, return first)
edge case -> if input is 00:00 -> ans is 00:00 (if use diff, this one will be "", but current way is fine)

00 00 
11.59 

00
09

20
 3 
 


1934

> 4 -> only 9


2359

23:53

22:53

22:22

22:29

4*4*4*4


new time - old time
2222 - 2359

0100 - 1111

 */
```