C++ recursive solution


  • 35
    J
    1. in the first pass I record counts of every character in a hashmap
    2. in the second pass I locate the first character that appear less than k times in the string. this character is definitely not included in the result, and that separates the string into two parts.
    3. keep doing this recursively and the maximum of the left/right part is the answer.
        int longestSubstring(string s, int k) {
            if(s.size() == 0 || k > s.size())   return 0;
            if(k == 0)  return s.size();
            
            unordered_map<char,int> Map;
            for(int i = 0; i < s.size(); i++){
                Map[s[i]]++;
            }
            
            int idx =0;
            while(idx <s.size() && Map[s[idx]] >= k)    idx++;
            if(idx == s.size()) return s.size();
            
            int left = longestSubstring(s.substr(0 , idx) , k);
            int right = longestSubstring(s.substr(idx+1) , k);
            
            return max(left, right);
            
        }
    

  • 0
    L

    easy to understand!


  • 0
    A

    What is the run time complexity of above algorithm ?


  • 2
    Y

    @akshay89 I guess worst case O(n^2), average O(n log n). In each recursion level, we scan the whole string, which is O(n). There will be at most n levels, e.g., k = 2 and every character in s appears exactly once. On average, there are log n levels.


  • 2
    B

    Good idea.
    I think you can skip the front elements with map[s[i]] < k to save time.

    int longestSubstring(string s, int k) {
        if(s.size() == 0 || k > s.size())   return 0;
        if(k == 0)  return s.size();
        
        unordered_map<char,int> Map;
        for(int i = 0; i < s.size(); i++){
            Map[s[i]]++;
        }
        
        int i = 0; 
        while(i<s.size() && Map[s[i]] >= k)    i++;      
        if(i == s.size()) return 0;
    
        int idx =i;
        while(idx <s.size() && Map[s[idx]] >= k)    idx++;
        if(idx == s.size()) return s.size() - i;
        
        int left = longestSubstring(s.substr(i , idx) , k);
        int right = longestSubstring(s.substr(idx+1) , k);
        
        return max(left, right);
        
    }

  • 0

    @james348021012 Your code gets TLE now.

    My refined version

    class Solution {
    public:
        int longestSubstring(string s, int k) {
            unordered_map<char, int> cnt;
            for (char c : s) cnt[c]++;
            int i = 0, j = 0, ans = 0;
            while (i < s.size()) {
                unordered_map<char, int> added;
                while (i < s.size() && cnt[s[i]] < k) ++i;
                j = i;
                while (j < s.size() && cnt[s[j]] + added[s[j]] >= k) {
                    added[s[j]]++;
                    cnt[s[j]]--;
                    ++j;
                }
                bool valid = true;
                for (char c = 'a'; c <= 'z' && valid; ++c) {
                    if (added[c] != 0 && added[c] < k) valid = false;
                }
                if (valid) ans = max(ans, j - i);
                else ans = max(ans, longestSubstring(s.substr(i, j - i), k));
                i = j;
            }
            return ans;
        }
    };
    

  • 4
    M

    now your solution is Time Limit Exceeded, I found the reason, but I don't know why. When change the type of Map to int Maps[26], the solution will be accepted.

    int longestSubstring(string s, int k) {
    if(s.size() == 0 || k > s.size()) return 0;
    if(k == 0) return s.size();

        int Map[26] = {0};
        for(int i = 0; i < s.size(); i++){
            Map[s[i]-'a']++;
        }
        
        int idx =0;
        while(idx <s.size() && Map[s[idx]-'a'] >= k)    idx++;
        if(idx == s.size()) return s.size();
        
        int left = longestSubstring(s.substr(0 , idx) , k);
        int right = longestSubstring(s.substr(idx+1) , k);
        
        return max(left, right);
        
    }

  • 0
    P

    This can be further optimized.
    When we recurse on the string, we partition and act on the first partition itself!.

    that is
    rec = max(rec(f(substring_after_first_invalid)), rec(string_before_first_invalid))

    Instead, we can do this
    rec = max(rec(substring_before_first_invalid), rec(substring_from_first_invalid_to_secnd_invalid), rec(substring_from_second_to_third), ...rec(substr(n - 1 _ to _ n)))


  • 0
    This post is deleted!

  • 4
    G

    The code can be optimized and the TLE can be fixed by adding just one more line before int right = ....

        int longestSubstring(string s, int k) {
            int n = (int)s.length();
            unordered_map<char, int> count;
            for (char c : s) ++count[c];
            int mid = 0;
            while (mid < n && count[s[mid]] >= k) ++mid;
            if (mid == n) return n;
            int left = longestSubstring(s.substr(0, mid), k);
            while (mid < n && count[s[mid]] < k) ++mid;
            int right = longestSubstring(s.substr(mid), k);
            return max(left, right);
        }
    

  • 0
    1

    @james348021012 good!


  • 0
    H

    @garygao1993 Very excellent refinement!


Log in to reply
 

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