Compute Longest Substring with At Least K Repeating Characters via Divide and Conquer Algorithm

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

Example 1:
Input: s = “aaabb”, k = 3
Output: 3
Explanation: The longest substring is “aaa”, as ‘a’ is repeated 3 times.

Example 2:
Input: s = “ababbc”, k = 2
Output: 5
Explanation: The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.

Constraints:
1 <= s.length <= 104
s consists of only lowercase English letters.
1 <= k <= 105

Divide and Conquer Strategy to Compute the Longest Substring with A Least K Repeating Characters

If a character is less than K in the string, it must not be in the longest substring, thus, we can use this character to divide the string into two half and recursively conquers/solves it.

C++ implementation of Divide and Conquer to compute the longest substring:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public:
    int longestSubstring(string s, int k) {
        unordered_map<char, int> freq;
        for (auto &n: s) {
            freq[n] ++;
        }
        for (auto &[a, b]: freq) {
            if (b < k) {
                int i = 0;
                while (i < s.size() && (s[i] != a)) i ++;
                return max(longestSubstring(s.substr(0, i), k), longestSubstring(s.substr(i + 1), k));
            }
        }
        return s.size();
    }
};

class Solution {
    public:
    int longestSubstring(string s, int k) {
        unordered_map<char, int> freq;
        for (auto &n: s) {
            freq[n] ++;
        }
        for (auto &[a, b]: freq) {
            if (b < k) {
                int i = 0;
                while (i < s.size() && (s[i] != a)) i ++;
                return max(longestSubstring(s.substr(0, i), k), longestSubstring(s.substr(i + 1), k));
            }
        }
        return s.size();
    }
};

The time complexity is O(N^2) as the spliting could take N times and for each split, we need to count the frequencies of characters. Although in most/practical cases, the algorithm performs better than O(N^2). The space complexity is O(N).

Python code of the same algorithm, but using the inbuilt count function:

1
2
3
4
5
6
7
8

class Solution(object):
    def longestSubstring(self, s, k):
        if not s:
            return 0
        for c in set(s):
            if s.count(c) < k:
                return max(self.longestSubstring(t, k) for t in s.split(c))
        return len(s)

class Solution(object):
    def longestSubstring(self, s, k):
        if not s:
            return 0
        for c in set(s):
            if s.count(c) < k:
                return max(self.longestSubstring(t, k) for t in s.split(c))
        return len(s)

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) --