Teaching Kids Programming – Divide and Conquer Algorithm to Find Longest Substring with Character Count of at Least K

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a lowercase alphabet string s and an integer k, return the length of the longest substring such that every character appears at least k times.

Constraints
k ≤ n ≤ 100,000 where n is the length of s
Example 1
Input
s = “abccddeefg”
k = 2
Output
6
Explanation
The longest substring here is “ccddee” and every character appears at least 2 times.

Hints:
If a character doesn’t satisfy the given condition, you need to process only those segments of string which doesn’t have that character. Think in terms of Divide and Conquer paradigm.

Longest Substring with Character Count of at Least K via Bruteforce Algorithm

We can bruteforce each substrings in O(N^2) time and then check each substring to see if it satisfies the requirement: each character appears at least K times O(N) time. The overall time complexity is O(N^3) and the space complexity is O(N) as we are using a Counter object.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def longestSubstringAtLeastK(self, s, k):
        n = len(s)
        ans = 0
        for i in range(n):
            for j in range(i, n):
                x = s[i:j+1]
                c = Counter(x)
                if min(c.values()) >= k:
                    ans = max(ans, j-i+1)
        return ans

class Solution:
    def longestSubstringAtLeastK(self, s, k):
        n = len(s)
        ans = 0
        for i in range(n):
            for j in range(i, n):
                x = s[i:j+1]
                c = Counter(x)
                if min(c.values()) >= k:
                    ans = max(ans, j-i+1)
        return ans

Longest Substring with Character Count of at Least K via Divide and Conquer Algorithm

If a character appears less than K times, then it must not be included in the longest satisified substring. Thus, we can use the invalid character to split the string into several groups and recursively conquer it. The longest substring each character appears at least K times should then be from group of strings split by the invalid character.

1
2
3
4
5
6

class Solution:
    def longestSubstringAtLeastK(self, s, k):
        for c, count in Counter(s).items():
            if count < k:
                return max(self.solve(x, k) for x in s.split(c))
        return len(s)

class Solution:
    def longestSubstringAtLeastK(self, s, k):
        for c, count in Counter(s).items():
            if count < k:
                return max(self.solve(x, k) for x in s.split(c))
        return len(s)

The time complexity is O(N). The space complexity is O(N) from the Counter and the stack.

Longest Substring Algorithms

• Teaching Kids Programming – Longest Substring Without Repeating Characters – Another Version of Two Pointer / Sliding Window Algorithm
• Teaching Kids Programming – Divide and Conquer Algorithm to Find Longest Substring with Character Count of at Least K
• Teaching Kids Programming – Longest Substring with 2 Distinct Characters by Sliding Window Algorithm
• Compute Longest Substring with At Least K Repeating Characters via Divide and Conquer Algorithm
• Two Pointer Sliding Window to Compute the Longest Substring with At Most Two Distinct Characters
• Two Pointer with Sliding Window Algorithm to Compute the Longest Substring with At Most K Distinct Characters

–EOF (The Ultimate Computing & Technology Blog) —