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.
1def longestSubstring(s: str, k: int) -> int:
2 if len(s) == 0 or k > len(s):
3 return 0
4 if k <= 1:
5 return len(s)
6
7 char_count = {}
8
9 for char in s:
10 if char in char_count:
11 char_count[char] += 1
12 else:
13 char_count[char] = 1
14
15 for char in char_count:
16 if char_count[char] < k:
17 return max(longestSubstring(subs, k) for subs in s.split(char))
18
19 return len(s)
20This implementation uses a hashmap to count occurrences of each character in the input string. If any character's count is less than k, it splits the string into substrings around each such character. It recursively calls itself for each of these substrings, and finally, returns the maximum length found. Base conditions handle edge cases like empty strings and where k is less than or equal to one.
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.