Longest Substring with At Most K Distinct Characters

Given a string s and an integer k, find the length of the longest substring that contains at most k distinct characters.

Example

Input: s = eceba, k = 2 Output: 3 (the substring ece)

Approach

Sliding window with a frequency map. Expand right, adding to the map; while the map has more than k distinct keys, shrink from the left, decrementing (and removing when zero) counts.

Input format

Line 1: s Line 2: k