Longest Substring with Limited Frequency Diversity — Problem Statement & Solution Guide
Problem Description
Given a string s and an integer k, return the maximum length of a substring of s such that the number of distinct frequencies of characters in the substring is at most k.
Examples
Input
aab, k = 2
Output
2
Explanation: Step-by-step: with input 'aab' and k = 2, we can see that the substring 'aa' has a frequency of {2}, and the substring 'ab' has a frequency of {1, 1}. Both of these substrings have at most 2 distinct frequencies, so the maximum length of a valid substring is 2.
Input
abaccc, k = 1
Output
6
Explanation: Step-by-step: with input 'abaccc' and k = 1, we can see that the substring 'abaccc' has a frequency of {1, 1, 1, 1, 1, 1}, which has only 1 distinct frequency. Therefore, the maximum length of a valid substring is 6.
Constraints
- 1 <= s.length <= 5 * 10^4
- 1 <= k <= 26
- s consists only of lowercase English letters.
Optimal Approach & Strategy
Using a sliding window with two maps (one for char frequencies, one for frequency-of-frequencies) allows constant time updates as the window expands and shrinks. This reduces the time complexity to O(n) because each character is added and removed from the window at most once.
Brute Force Approach
The brute-force approach involves generating all possible substrings using nested loops, which results in O(n^2) substrings. For each substring, you calculate the frequency of characters and check if the count of distinct frequencies is less than or equal to k, leading to an overall O(n^3) complexity.
Verified Code Solutions
class Solution {
public int longestSubstring(String s, int k) {
int max_length = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
String substring = s.substring(i, j);
int[] freq = new int[26];
for (char c : substring.toCharArray()) {
freq[c - 'a']++;
}
int distinct_freq = 0;
for (int count : freq) {
if (count > 0) {
distinct_freq++;
}
}
if (distinct_freq <= k) {
max_length = Math.max(max_length, substring.length());
}
}
}
return max_length;
}
}def longest_substring(s, k):
max_length = 0
for i in range(len(s)):
for j in range(i + 1, len(s) + 1):
substring = s[i:j]
freq = {}
for char in substring:
if char in freq:
freq[char] += 1
else:
freq[char] = 1
distinct_freq = set()
for count in freq.values():
distinct_freq.add(count)
if len(distinct_freq) <= k:
max_length = max(max_length, len(substring))
return max_lengthAsked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.