K-Distinct Topic Window
A topic classifier tags each message in a chat stream with a topic id. To find the longest coherent conversation segment, you want the longest contiguous run of messages that touches at most k distinct topics. The DSA underneath is a classic variable-size window — the topic tags are just the data.
Problem
Given an array topics of topic ids and an integer k, return the length of the longest contiguous subarray containing at most k distinct values.
Input
An array topics of length n (1 ≤ n ≤ 10^5) and integer k (1 ≤ k ≤ n).
Output
A single integer — the length of the longest qualifying window.
Constraints
- 1 ≤ k ≤ n ≤ 100,000
- Topic ids in [0, 10^9]
- At most k distinct values inside the window
Examples
Example 1
Input
topics = [1, 2, 1, 2, 3], k = 2
Output
4
[1, 2, 1, 2] uses 2 distinct topics; adding the 3 would make 3, so the run stops at length 4.
Example 2
Input
topics = [1, 2, 3], k = 1
Output
1
With only one distinct topic allowed, no two adjacent differing topics can coexist.