C++ Recursive solution


  • 0

    If there are letters with frequency less than k. This character can not be in the longest substring. Let us use B to represent letters with frequency less than k and A for frequency larger than k.

    For a string such as:
    (AA...AA)B(AA...AA)B(AA...AA)

    The new problem is finding longest substring in the 3 (AA...AA) part. This will be a natural recursive structure.

    Now the problem is when to stop recursion.

    1. If your current string is already shorter than k.
    2. When all the letters in this substring has frequency larger than k. Then this substring is a valid candidate. we can compare it to max_len.

    And for initialization, we set max_len to be k-1 since the smallest valid longest substring should be k.

    class Solution {
    public:
        int longestSubstring(string s, int k) {
            int ret = k-1;
            longest(s, k, 0, s.size()-1, ret);
            
            return ret == k-1 ? 0 : ret;
        }
        
        void longest(string str, int k, int s, int e, int& max_len) {
            if(s > e || e-s+1 < max_len) {
                return;
            }
            
            // Consider which are valid letters
            vector<int> freq(26, 0);
            for(int i = s; i <= e; ++i) {
                freq[str[i]-'a'] += 1;
            }
            
            // when all the letters are >= k
            bool satisfy = true;
            for(int i = 0; i < 26; ++i) {
                if(freq[i] > 0 && freq[i] < k) {
                    satisfy = false;
                }
            }
            // all letters >= k
            if(satisfy) {
                max_len = max(e-s+1, max_len);
                return;
            }
            
            // otherwise, we generate smaller piece of substrings
            for(int p = s; p <= e; ){
                int len = 0;
                // expand as much as possible
                while(p+len <= e && freq[str[p+len]-'a'] >= k) {
                    len += 1;
                }
                
                longest(str, k, p, p+len-1, max_len);
                p += len+1;
            }
        }
        
    };
    

Log in to reply
 

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