Longest Substring with Limited Frequency Diversity — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Strings and solve the Longest Substring with Limited Frequency Diversity problem optimally.
O(n)O(n)Problem Description
You are provided with a string s consisting of lowercase English letters and an integer k. Your task is to determine the maximum length of a contiguous substring of s such that the number of distinct character frequencies within that substring is at most k.
For any given substring, calculate the frequency of each character present. Then, identify the set of unique frequency values. If the size of this set is less than or equal to k, the substring is valid. Return the length of the longest valid substring. If no such substring exists (which is impossible for k >= 1 and non-empty s, but logically covers edge cases), return 0.
Note: A character with frequency 0 is not considered 'present' in the substring, so its frequency is not included in the diversity count. Only characters that appear at least once contribute to the frequency set.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Longest Substring with Limited Frequency Diversity"
WHY DOES IT MATTER?
The sliding window with auxiliary frequency tracking is a classic pattern for substring problems where a global property (here, the number of distinct frequencies) must be maintained efficiently. It avoids repeated recomputation and guarantees linear time, which is critical for large inputs.
OPTIMIZATION CHALLENGE
The key insight is that the number of distinct frequencies can be updated in O(1) by maintaining a count of how many characters have each frequency. This eliminates the need to recompute the set of frequencies from scratch after each window adjustment.
REAL-WORLD CONNECTION
Consider a distributed log system that aggregates event counts per service. To detect periods where the diversity of event frequencies stays below a threshold, the same sliding window technique can be applied to rolling windows of log entries.
When implementing, always update the frequency‑count array before checking the distinct‑frequency condition. Off‑by‑one errors in updating counts when a character’s frequency drops to zero are a common pitfall.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem asks for the longest contiguous substring where the set of character frequencies contains at most *k* distinct values. A naive solution would enumerate all substrings, compute frequencies for each, and check the distinct‑frequency count, leading to an O(n^3) time complexity (O(n^2) substrings times O(n) frequency calculation). This is infeasible for strings of length 10^5. The optimal solution uses a two‑pointer sliding window that expands the right boundary while maintaining two auxiliary arrays: one for the frequency of each letter (size 26) and one for the count of each frequency value (size up to the current window length). By updating these arrays in O(1) per character, we can keep track of how many distinct frequencies are present. When that number exceeds *k*, we shrink the window from the left, again updating the arrays in O(1). This yields an overall O(n) time and O(n) space solution, which is optimal because each character is processed a constant number of times.
Interview Questions on This Problem
Q1How would you modify the sliding window approach if the string contained uppercase letters as well?
Extend the frequency array to size 52 (or use a map) to account for both cases. The rest of the algorithm remains identical, as the window logic depends only on frequency counts, not on the alphabet size.
Q2A fintech platform needs to detect anomalous transaction patterns within a stream of transaction types. How does this problem relate to that scenario?
The transaction types can be mapped to characters, and the goal of finding a longest segment with limited frequency diversity is analogous to finding a period where transaction types exhibit controlled variability, which can indicate normal behavior versus anomalies.
Q3During a high‑growth startup interview, you are asked to explain why maintaining a separate frequency‑count array is more efficient than recomputing frequencies each time the window changes. What would you say?
Recomputing frequencies would require scanning the window, leading to O(n^2) time. A frequency‑count array allows constant‑time updates when adding or removing a character, ensuring the sliding window runs in linear time.
Examples
Input
s = "aabbc", k = 1
Output
2
Explanation: Consider the substring "aabb". Frequencies: a=2, b=2. Distinct frequencies: {2}. Size = 1 <= 1. Valid. Length = 4. Consider "aabbc": a=2, b=2, c=1. Distinct frequencies: {2, 1}. Size = 2 > 1. Invalid. The longest valid substring is "aabb" or "bb" (length 2) or "aa" (length 2). Max length is 4.
Input
s = "abcabc", k = 2
Output
6
Explanation: Consider the entire string "abcabc". Frequencies: a=2, b=2, c=2. Distinct frequencies: {2}. Size = 1 <= 2. Valid. Length = 6. Since the entire string is valid, the answer is 6.
Input
s = "ababab", k = 1
Output
2
Explanation: Consider the entire string "ababab". Frequencies: a=3, b=3. Distinct frequencies: {3}. Size = 1 <= 1. Valid. Length = 6. The answer is 6.
Input
s = "aabbcc", k = 1
Output
2
Explanation: Consider "aabb": a=2, b=2. Distinct freqs: {2}. Size 1 <= 1. Valid. Length 4. Consider "aabbcc": a=2, b=2, c=2. Distinct freqs: {2}. Size 1 <= 1. Valid. Length 6. Wait, let's re-evaluate. "aabbcc" has a=2, b=2, c=2. Distinct frequencies are {2}. Size is 1. So length 6 is valid. Let's pick a better example for k=1 where it's not the whole string. Let's use s="aabbc", k=1 again? No, already used. Let's use s="aaabbb", k=1. Frequencies: a=3, b=3. Distinct {3}. Size 1. Length 6. Let's use s="aaabb", k=1. "aaabb": a=3, b=2. Distinct {3,2}. Size 2 > 1. "aaab": a=3, b=1. Distinct {3,1}. Size 2 > 1. "aaa": a=3. Distinct {3}. Size 1. Length 3. "aab": a=2, b=1. Distinct {2,1}. Size 2. "abb": a=1, b=2. Distinct {1,2}. Size 2. "bb": b=2. Distinct {2}. Size 1. Length 2. Max is 3. Let's use s="aaabb", k=1. Output 3.
Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters only
- 1 <= k <= 26
Optimal Approach & Strategy
Use a sliding window with two frequency arrays: one for character counts and one for counts of those frequencies. Expand the window, update arrays in O(1), and shrink when distinct frequencies exceed *k*. This runs in O(n) time.
Brute Force Approach
Enumerate all substrings, compute character frequencies for each, count distinct frequency values, and keep the maximum length. This takes O(n^3) time and is impractical for large strings.
Code Solutions
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var longestSubstringWithLimitedFrequencyDiversity = function(s, k) {
const n = s.length;
if (n === 0) return 0;
const freq = new Array(26).fill(0);
const freqCount = new Map();
let left = 0;
let maxLen = 0;
for (let right = 0; right < n; right++) {
const idx = s.charCodeAt(right) - 'a'.charCodeAt(0);
if (freq[idx] > 0) {
freqCount.set(freq[idx], freqCount.get(freq[idx]) - 1);
if (freqCount.get(freq[idx]) === 0) {
freqCount.delete(freq[idx]);
}
}
freq[idx]++;
freqCount.set(freq[idx], (freqCount.get(freq[idx]) || 0) + 1);
while (freqCount.size > k) {
const leftIdx = s.charCodeAt(left) - 'a'.charCodeAt(0);
freqCount.set(freq[leftIdx], freqCount.get(freq[leftIdx]) - 1);
if (freqCount.get(freq[leftIdx]) === 0) {
freqCount.delete(freq[leftIdx]);
}
freq[leftIdx]--;
if (freq[leftIdx] > 0) {
freqCount.set(freq[leftIdx], (freqCount.get(freq[leftIdx]) || 0) + 1);
}
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
};class Solution {
public:
int longestSubstringWithLimitedFrequencyDiversity(string s, int k) {
int n = s.size();
if (n == 0) return 0;
vector<int> freq(26, 0);
unordered_map<int, int> freqCount;
int left = 0;
int maxLen = 0;
for (int right = 0; right < n; ++right) {
int idx = s[right] - 'a';
if (freq[idx] > 0) {
freqCount[freq[idx]]--;
if (freqCount[freq[idx]] == 0) {
freqCount.erase(freq[idx]);
}
}
freq[idx]++;
freqCount[freq[idx]]++;
while (freqCount.size() > k) {
int leftIdx = s[left] - 'a';
freqCount[freq[leftIdx]]--;
if (freqCount[freq[leftIdx]] == 0) {
freqCount.erase(freq[leftIdx]);
}
freq[leftIdx]--;
if (freq[leftIdx] > 0) {
freqCount[freq[leftIdx]]++;
}
left++;
}
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}
};class Solution {
public int longestSubstringWithLimitedFrequencyDiversity(String s, int k) {
int n = s.length();
if (n == 0) return 0;
int[] freq = new int[26];
Map<Integer, Integer> freqCount = new HashMap<>();
int left = 0;
int maxLen = 0;
for (int right = 0; right < n; right++) {
int idx = s.charAt(right) - 'a';
if (freq[idx] > 0) {
freqCount.put(freq[idx], freqCount.get(freq[idx]) - 1);
if (freqCount.get(freq[idx]) == 0) {
freqCount.remove(freq[idx]);
}
}
freq[idx]++;
freqCount.put(freq[idx], freqCount.getOrDefault(freq[idx], 0) + 1);
while (freqCount.size() > k) {
int leftIdx = s.charAt(left) - 'a';
freqCount.put(freq[leftIdx], freqCount.get(freq[leftIdx]) - 1);
if (freqCount.get(freq[leftIdx]) == 0) {
freqCount.remove(freq[leftIdx]);
}
freq[leftIdx]--;
if (freq[leftIdx] > 0) {
freqCount.put(freq[leftIdx], freqCount.getOrDefault(freq[leftIdx], 0) + 1);
}
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}class Solution:
def longestSubstringWithLimitedFrequencyDiversity(self, s: str, k: int) -> int:
n = len(s)
if n == 0:
return 0
freq = [0] * 26
freq_count = {}
left = 0
max_len = 0
for right in range(n):
idx = ord(s[right]) - ord('a')
if freq[idx] > 0:
freq_count[freq[idx]] -= 1
if freq_count[freq[idx]] == 0:
del freq_count[freq[idx]]
freq[idx] += 1
freq_count[freq[idx]] = freq_count.get(freq[idx], 0) + 1
while len(freq_count) > k:
left_idx = ord(s[left]) - ord('a')
freq_count[freq[left_idx]] -= 1
if freq_count[freq[left_idx]] == 0:
del freq_count[freq[left_idx]]
freq[left_idx] -= 1
if freq[left_idx] > 0:
freq_count[freq[left_idx]] = freq_count.get(freq[left_idx], 0) + 1
left += 1
max_len = max(max_len, right - left + 1)
return max_len/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var longestSubstringWithLimitedFrequencyDiversity = function(s, k) {
const n = s.length;
if (n === 0) return 0;
const freq = new Array(26).fill(0);
const freqCount = new Map();
let left = 0;
let maxLen = 0;
for (let right = 0; right < n; right++) {
const idx = s.charCodeAt(right) - 'a'.charCodeAt(0);
if (freq[idx] > 0) {
freqCount.set(freq[idx], freqCount.get(freq[idx]) - 1);
if (freqCount.get(freq[idx]) === 0) {
freqCount.delete(freq[idx]);
}
}
freq[idx]++;
freqCount.set(freq[idx], (freqCount.get(freq[idx]) || 0) + 1);
while (freqCount.size > k) {
const leftIdx = s.charCodeAt(left) - 'a'.charCodeAt(0);
freqCount.set(freq[leftIdx], freqCount.get(freq[leftIdx]) - 1);
if (freqCount.get(freq[leftIdx]) === 0) {
freqCount.delete(freq[leftIdx]);
}
freq[leftIdx]--;
if (freq[leftIdx] > 0) {
freqCount.set(freq[leftIdx], (freqCount.get(freq[leftIdx]) || 0) + 1);
}
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
};Asked 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.