Divide and Conquer c++ solution


  • 0
    1. Traverse once, find all indexes where the count of char is below k.
    2. Recursively deal with all intervals between those indexes.
    int longestSubstring(string s, int k) {
            return longestSubstring(s, k, 0, s.size() - 1);
        }
        
    int longestSubstring(string &s, int k, int i, int j) {
            if (i > j)
                return 0;
            int count[128] = {0};
            int result = 0;
            for (int index = i; index <= j; index++) {
                count[s[index]]++;
            }
            int start = i;
            for (int index = i; index <= j; index++) {
                if (count[s[index]] < k) {
                    result = max(result, longestSubstring(s, k, start, index - 1));
                    start = index + 1;
                }
            }
            if (start == i)
                result = j - i + 1;
            else
                result = max(result, longestSubstring(s, k, start, j));
            return result;
        }
    

Log in to reply
 

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