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.
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4#include <string>
5using namespace std;
int longestSubstring(string s, int k) {
int maxLen = 0;
for (int numUnique = 1; numUnique <= 26; ++numUnique) {
unordered_map<char, int> countMap;
int start = 0, end = 0, uniqueCount = 0, countAtLeastK = 0;
while (end < s.size()) {
if (uniqueCount <= numUnique) {
char c = s[end];
if (countMap[c]++ == 0) uniqueCount++;
if (countMap[c] == k) countAtLeastK++;
end++;
} else {
char c = s[start];
if (countMap[c]-- == k) countAtLeastK--;
if (countMap[c] == 0) uniqueCount--;
start++;
}
if (uniqueCount == numUnique && uniqueCount == countAtLeastK) {
maxLen = max(maxLen, end - start);
}
}
}
return maxLen;
}The C++ solution employs two pointers to define the window's start and end. It iterates over possible unique character counts and uses a hashmap to track character frequency. It expands the window by moving the end pointer and contracts by moving the start if constraints are violated. The current valid window's length gets evaluated against the maximum length found so far.