Sponsored
Sponsored
This approach uses recursion to divide the string into smaller parts based on characters that do not meet the frequency threshold k. The recursive function checks the entire string and divides it at points where a character occurs fewer than k times. The algorithm then recursively checks each of these substrings, calculating the longest valid substring length for each, and returns the maximum of these lengths.
Time Complexity: O(n log n), where n is the length of the string, due to string splitting and recursion.
Space Complexity: O(n), for the recursion stack and character frequency hashmap.
1function longestSubstring(s, k) {
2 if (s.length === 0 || k > s.length) return 0;
3 if (k <= 1) return s.length;
4
5 const charCount = {};
6
7 for (let char of s) {
8 charCount[char] = (charCount[char] || 0) + 1;
9 }
10
11 for (let char in charCount) {
12 if (charCount[char] < k) {
13 return Math.max(...s.split(char).map(sub => longestSubstring(sub, k)));
14 }
15 }
16
17 return s.length;
18}Similar to the Python solution, this implementation uses an object to keep track of character frequencies. It splits the string at characters that don't meet the minimum frequency requirement and recursively processes each part to find the maximum valid substring length.
This approach works by using the sliding window technique. The idea is to maintain a window with a maximum unique count of characters and check if the conditions are met for each window. The algorithm adjusts the window boundaries to ensure all characters within the window occur at least k times.
Time Complexity: O(n), as each character is processed at most twice.
Space Complexity: O(1), as the space used by the character frequency array is constant.
1import java.util.HashMap;
2
In this Java solution, similar to the C++ version, a sliding window is implemented with two pointers iterating through possible unique characters. A hashmap provides the tracking mechanism for character frequencies within the window. The variable numUnique defines the distinct character limits being considered for each iteration.