Smallest Subarray with K Diverse and M Limited Characters
At Groww, understanding user behavior is key to personalizing experiences. Imagine we're analyzing sequences of user interactions, represented as a string of characters (e.g., product views, searches, or clicks). We want to identify the smallest contiguous segment of these interactions that demonstrates a specific level of diversity (at least k distinct types of interactions) while ensuring no single interaction type dominates excessively (appearing more than m times). This helps us pinpoint focused yet varied user intent without noise from overly repetitive actions, optimizing content recommendations or feature prioritization.
Implement a function findSmallestSubarray that takes a string s (representing a sequence of user interactions), an integer k (minimum number of distinct interaction types), and an integer m (maximum allowed frequency for any single interaction type).
The function should return the length of the smallest contiguous subarray (substring) of s that satisfies both of the following conditions:
k distinct characters.m times.s: A string consisting only of lowercase English letters ('a'-'z').k: An integer representing the minimum number of distinct characters required in the subarray.m: An integer representing the maximum allowed frequency for any single character within the subarray.s is empty? The problem constraints specify s.length >= 1, so s will not be empty.k or m are outside their specified ranges? Assume inputs are within constraints.s only contains lowercase English letters.Examples
Example 1
Input:
s = "aabcbebbac", k = 3, m = 2
Output:
3
Note:
The smallest valid subarray is "abc" (from index 1 to 3). It has length 3, contains 3 distinct characters ('a', 'b', 'c'), and no character appears more than 1 time (which is <= m=2).
Example 2
Input:
s = "abacaba", k = 2, m = 1
Output:
2
Note:
With m=1, no character can repeat. Subarrays like "ab" or "ba" have length 2, 2 distinct characters, and max frequency 1. "aba" would be invalid because 'a' repeats.
Example 3
Input:
s = "zzzyyy", k = 3, m = 2
Output:
-1
Note:
The string only contains two distinct characters ('z', 'y'). It's impossible to form a subarray with at least 3 distinct characters.
Constraints
1 <= s.length <= 10^51 <= k <= 26 (since s consists of lowercase English letters)1 <= m <= s.lengths consists only of lowercase English letters ('a'-'z').s.length.k and m values.k or m are at their extremes.Loading editor...