C++ AC O(nlogn)solution using divide and conquer with detailed explaination


  • 0
    F

    The idea is as follows.
    Get the indexes of the character whose frequency in the string is less than k in string s, then we can narrow the range of the potential strings from the indexes we get. Finally we can solve this problem recursively.

    For example,
    string s : aaaaccbbcccd k = 3

    indexes [6,7,11] potential strings [aaaacc, ccc]

    for string : aaaacc ,
    index [4] potential strings [aaaa] result = 4 in this case
    for string ccc,
    index [] potential strings [ccc] result = 3 in this case
    Finally we get 4 :)

    class Solution {
    public:
        int longestSubstring(string s, int k) {
            if(s.size() < k) return 0;
            if(least_times(s) >= k) return (int) s.size();
            unordered_map<char,int> m; // char -> freq
            int result = 0;
            vector<int> indexes;
            for(int i = 0;i<s.size();i++){
                m[s[i]]++;
            }
            for(int i = 0;i<s.size();i++){
                if(m[s[i]] < k) indexes.push_back(i);
            }
            int start = 0;
            for(int i = 0; i < indexes.size();i++){
                string potential = s.substr(start,indexes[i] - start);
                start = indexes[i] + 1;
                result = max(result, longestSubstring(potential,k));
            }
            string potential = s.substr(start,s.size() - start);
            result = max(result, longestSubstring(potential,k));
            return result;
        }
        int least_times(string a){ // calculate least time of a string
            if(a.empty()) return 0;
            unordered_map<char,int> m; // char -> freq
            int r = INT_MAX;
            for(int i = 0;i<a.size();i++){
                m[a[i]]++;
            }
            for(auto iter = m.begin();iter!=m.end();++iter){
                r = min(r, iter->second);
            }
            return r;
        }
    };
    

  • 0
    H

    You using map so it's o(nlgn)but not o(n)


  • 0
    F
    This post is deleted!

  • 0
    F

    @huangweiwei unordered_map is a hash map, but by master theorem(a = b and f(n) = O(n)), this solution is O(nlogn). You are right. I have edited my title.


Log in to reply
 

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