Frontend School

Smallest Subarray with K Diverse and M Limited Characters

DSA
hard

Smallest Subarray with K Diverse and M Limited Characters

Hard
Sliding Window
Hash Map
String

Overview

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.

What you need to do / Task

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:

  1. The subarray contains at least k distinct characters.
  2. No character within the subarray appears more than m times.

Input & output

  • 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.
  • Returns: An integer, the length of the smallest valid subarray. If no such subarray exists, return -1.

Clarifications

  • What if s is empty? The problem constraints specify s.length >= 1, so s will not be empty.
  • What if k or m are outside their specified ranges? Assume inputs are within constraints.
  • Characters are case-sensitive? No, s only contains lowercase English letters.
  • If multiple subarrays have the same smallest length, returning the length of any one is sufficient.

Examples

1

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).

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.

3

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

Constraints & assumptions

  • 1 <= s.length <= 10^5
  • 1 <= k <= 26 (since s consists of lowercase English letters)
  • 1 <= m <= s.length
  • s consists only of lowercase English letters ('a'-'z').
  • Expected time complexity: O(N) where N is s.length.
  • Expected space complexity: O(1) (due to fixed alphabet size).

Out of scope

  • Handling non-alphabetic characters or uppercase letters.
  • Input validation for k and m values.

What interviewers evaluate

  • Correctness of the sliding window logic, effectively handling both distinct character count and max frequency constraints simultaneously.
  • Efficiency of the algorithm, achieving optimal time and space complexity.
  • Ability to handle various edge cases, such as when no valid subarray exists, or when k or m are at their extremes.
  • Clarity, readability, and modularity of the code structure.

Loading editor...