395.Longest Substring with At Least K Repeating Characters

Tags: [divide_conquer], [recursion]

Link: https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/?tab=Description

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Solution: divide conquer, recursion

class Solution(object):
    def longestSubstring(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        if not s:
            return 0

        c_map = {}
        for c in s:
            if c in c_map:
                c_map[c] += 1
            else:
                c_map[c] = 1

        for c in s:
            if c_map[c] < k:
                sub_strings = s.split(c)
                return max([self.longestSubstring(sub_str, k) for sub_str in sub_strings])

        return len(s)

Revelation:

• If the number of the char is less than k, that means the valid substring must not contain this char, which means, we can break the string by this char to multiple substring. So then we can do recursion on each substring and compare the result from each recursion.
• If the naive solution T = O(n^2) or T = O(n^3), we can think we may can optimize it to T = O(lgn), which means the optimization solution may be binary search, binary search tree, or divid conquer. But for this question, the time complexity is O(n + lgn) = O(n), because at the beginning of each recursion, it need count the chars. N

Note:

• I am not sure the time complexity is T = O(n + lgn) = O(n) or T = O(n + nlgn) = O(nlgn), n is the length of the given string.

Time Limited Exceeded

class Solution(object):
    def longestSubstring(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        if not s:
            return 0

        max_len = 0
        for start in xrange(len(s)):
            for end in xrange(start, len(s)):
                if self.is_valid(s, k, start, end):
                    max_len = max(max_len, (end - start + 1))

        return max_len

    def is_valid(self, s, k, start, end):
        c_map = {}
        for i in xrange(start, end + 1):
            c = s[i]
            if c in c_map:
                c_map[c] += 1
            else:
                c_map[c] = 1

        for c in c_map:
            if c_map[c] < k:
                return False

        return True

Note:

• Time complexity = O(n^3), n is the length of the given string.