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.
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4#include <string>
using 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.