Maximum Sum of Distinct Subarrays With Length K

Fixed window with distinctness

Slide a window of exactly k elements across the array. Maintain its numeric sum and a frequency map. Add the right value to both; once the window exceeds k, subtract the left value, decrement its frequency, and erase a key at zero. When the window length is k and the map has k keys, every element is distinct, so use the running sum to update the maximum. This avoids recomputing either property for each starting position.

Interview details

Explain why map size alone is sufficient only after window length is fixed: a size-k window with k distinct keys has no duplicate. Clarify what to return when no valid window exists, commonly zero or a sentinel depending on the statement, and use a wide integer for sums if values can be large. With hash-map operations amortized constant time, the algorithm is O(n) time and O(k) space. A set without counts is wrong because removing one copy could erase a value still inside the window.