Problem

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.

if no such substring exists, return 0.

Examples

Example 1:

1
2
3
4
5

Input:
s = "aaabb", k = 3
Output:
 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

1
2
3
4
5

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.

Solution

Method 1 - Recursion

To solve the problem of finding the length of the longest substring in s such that the frequency of each character in this substring is greater than or equal to k, the idea is to use a divide-and-conquer strategy.

Here are the steps:

  1. Frequency Calculation:
    • Calculate the frequency of each character in the string.
  2. Divide and Conquer:
    • If a character’s frequency is less than k, then this character cannot be part of the valid substring. This splits the problem into smaller substrings.
    • Recursively check each of these substrings to find the longest valid substring.
  3. Base Case:
    • If every character in the string meets the frequency requirement, return the length of the string.

Pseudo code

  • Define a recursive function that finds the longest valid substring.
  • Compute character frequencies for the given substring.
  • Identify split points where a character’s frequency is less than k.
  • Recurse into substrings formed by splitting at these points.
  • Return the maximum length found in these substrings.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {
    public int longestSubstring(String s, int k) {
        return longestSubstringHelper(s, 0, s.length(), k);
    }

    private int longestSubstringHelper(String s, int start, int end, int k) {
        if (end - start < k) return 0; // Base case: not enough length to meet k requirement
        
        int[] freq = new int[26];
        for (int i = start; i < end; i++) {
            freq[s.charAt(i) - 'a']++;
        }
        
        for (int i = start; i < end; i++) {
            if (freq[s.charAt(i) - 'a'] < k) {
                int j = i + 1;
                while (j < end && freq[s.charAt(j) - 'a'] < k) j++;
                return Math.max(longestSubstringHelper(s, start, i, k), longestSubstringHelper(s, j, end, k));
            }
        }
        
        return end - start; // All characters in this range meet the k requirement
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        return self._longestSubstring(s, 0, len(s), k)

    def _longestSubstring(self, s: str, start: int, end: int, k: int) -> int:
        if end - start < k:
            return 0  # Base case: not enough length to meet k requirement
        
        freq = [0] * 26
        for i in range(start, end):
            freq[ord(s[i]) - ord('a')] += 1
        
        for i in range(start, end):
            if freq[ord(s[i]) - ord('a')] < k:
                j = i + 1
                while j < end and freq[ord(s[j]) - ord('a')] < k:
                    j += 1
                return max(self._longestSubstring(s, start, i, k), self._longestSubstring(s, j, end, k))
        
        return end - start  # All characters in this range meet the k requirement

Complexity

  • Time: O(n*n) , which is O(n^2) because each recursive call processes a substring and can make further recursive calls proportional to the length of the substring.
  • Space: O(n), due to the recursion stack.