681. Next Closest Time

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 all valid. “1:34”, “12:9” are all invalid.

• Time : O(d^4 + klogk)
• Space : O(k)

c++

class Solution {
    vector<pair<int,int>> biggerCandidate, lowerCandidate;
    unordered_set<int> digit;
    pair<int,int> origin;
    bool valid(int num) {
        int hour = num / 100;
        int minute = num % 100;
        return 0 <= hour and hour <= 23 and 0 <= minute and minute < 60;
    }
    bool bigger(int num) {
        int hour = num / 100;
        int minute = num % 100;
        if(hour < origin.first) {
            return false;
        } else if(hour > origin.first) {
            return true;
        }
        return minute > origin.second;
    }
    void backTracking(int pick, int num) {
        if(pick == 4) {
            if(!valid(num)) return;
            if(bigger(num)) {
                biggerCandidate.push_back({ num / 100, num % 100});
            } else {
                lowerCandidate.push_back({ num / 100, num % 100});
            }

        } else {
            for(auto d : digit) {
                backTracking(pick + 1, num * 10 + d);
            }
        }
    }
public:
    string nextClosestTime(string time) {
        origin = {stoi(time.substr(0, time.find(':'))), stoi(time.substr(time.find(':') + 1))};

        for(auto ch : time)
            if(ch != ':') digit.insert(ch&0b1111);

        backTracking(0,0);

        if(!biggerCandidate.empty()) {
            sort(biggerCandidate.begin(), biggerCandidate.end());
            return (biggerCandidate[0].first <= 9 ? '0' + to_string(biggerCandidate[0].first) : to_string(biggerCandidate[0].first)) 
            + ':' 
            + (biggerCandidate[0].second <= 9 ? '0' + to_string(biggerCandidate[0].second) : to_string(biggerCandidate[0].second));
        } else {
            sort(lowerCandidate.begin(), lowerCandidate.end());
            return (lowerCandidate[0].first <= 9 ? '0' + to_string(lowerCandidate[0].first) : to_string(lowerCandidate[0].first)) 
            + ':' 
            + (lowerCandidate[0].second <= 9 ? '0' + to_string(lowerCandidate[0].second) : to_string(lowerCandidate[0].second));
        }

    }
};