10 lines C++ Solution, Clear and Simple (3ms)


  • 1
    W

    Solution 1

    From Java solution: https://discuss.leetcode.com/topic/57372/java-3ms-divide-and-conquer-recursion-solution

    int longestSubstring(const string &s, int k) {
        return helper(s, 0, s.size(), k);
    }
    int helper(const string &s, int beg, int end, int k){
        if(end - beg < k) return 0;
        int cnt[26]{};
        for(int i = beg; i < end; ++i) ++cnt[s[i]-'a'];
        for(int i = 0; i < 26; ++i)
            if (cnt[i] && cnt[i] < k)
                for(int j = beg; j < end; ++j)
                    if(s[j] == i + 'a')
                        return max(helper(s, beg, j, k), helper(s, j + 1, end, k));
        return end - beg;
    }
    

    Solution 2

    Less iterations, faster and shorter(8 lines):

    int longestSubstring(const string &s, int k) {
        return helper(s, 0, s.size(), k);
    }
    int helper(const string &s, int beg, int end, int k){
        if(end - beg < k) return 0;
        int cnt[26]{};
        for(int i = beg; i < end; ++i) ++cnt[s[i]-'a'];
        for(int i = beg; i < end; ++i)
            if (cnt[s[i] - 'a'] < k)
                return max(helper(s, beg, i, k), helper(s, i + 1, end, k));
        return end - beg;
    }
    

Log in to reply
 

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