C++, O(n), Divide and Conquer


  • 3
    Z

    In every step of DC, at least 1 character, let's say, 'a', is chosen to divide the string, then all substrings in following recursive calls have no 'a'. The level of DC is at most 26, otherwise you run out of character to divide, and each level is O(n). The run time is 3 ms.

    class Solution {
    public:
        int longestSubstring(string s, int k) {
            int n = s.size();
            return helper(s, 0, n-1, k);
        }
    private:
        // looking for longest string within index range [l, r]
        int helper(string& s, int l, int r, int k) {
            vector<int> mp(26, 0);
            for (int i = l; i <= r; i++) mp[s[i]-'a']++;
           // check whether the whole string meets requirement
            bool pass = true;
            for (int i = 0; i < 26 && pass; i++) {
                if (mp[i] && mp[i] < k)
                    pass = false;
            }
            if (pass) return r-l+1;
            // using all characters with occurrence > 0 && < k to divide the string
            int i = l, ans = 0;
            for (int j = l; j <= r; j++) {
                if (mp[s[j]-'a'] && mp[s[j]-'a'] < k) {
                    ans = max(ans, helper(s, i, j-1, k));
                    i = j+1;
                }
            }
            return max(ans, helper(s, i, r, k));
        }
    };
    

Log in to reply
 

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