C++ recursive solution


  • 36
    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;
        }
    };
    

  • 5
    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!


  • 0
    B

    @Mxiaoyu because of stack overflow!Not Time Limit Exceeded!
    when leetcode use a test case with a large string and a special k,and the string is also special,like"aaaaaa....bbbbbbb.......ccccc....zzzzz",this test case will lead to too many recursive invocations, and cause a stack overflow,but LeetCode just says “Time Limit Exceeded”.Changing the type of Map to int Maps[26] actually take up less memory,which happen to not touch the critical point of max stack memory even though in some special test case ,that is why Maps[26] is accepted and Map not.
    Besides,the original solution will be accepted sometimes and will be refused at other times,you can try it !. I think this is related to how LeetCode allocates the stack memory in each test. Also,for some special test case,visual studio 2017
    will run for a long time and report a error but Dev-c++ 5.11 can accept it quickly,because they allocate the stack memory differently!


Log in to reply
 

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