C++ 15lines divide and conquer beats 48.2%, clean code


  • 1
    T

    // idea: preprocess to build a char -> freq map.
    // scan the input to find a char that appears less than k.
    // then use that char as the delimiter to split the input.
    // Divide and conquer, recursively work on the split substrings (subproblems).

        int longestSubstring(string s, int k) {
            vector<int> char2count(128, 0);
            for(char c : s) char2count[c]++;
            for(int i = 0; i < s.length(); i++) {
                if(char2count[s[i]] > 0 && char2count[s[i]] < k) {
                    int start = 0, end;
                    stringstream ss(s);
                    string token = "";
                    int ans = 0;
                    while(getline(ss, token, s[i])) {
                        ans = max(ans, longestSubstring(token, k));
                    }
                    return ans;
                }
            }
            return s.length();
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.