Longest Substring with Exactly K Distinct Characters

Given a string s consisting of lowercase English letters and an integer k, find the length of the longest contiguous substring that contains exactly k distinct characters. If no such substring exists, output -1.

This problem tests your ability to efficiently apply the sliding window technique. For example, the sliding window invariant can be represented as: \( s[l \ldots r] \text{ such that } |\{s[l], s[l+1], \ldots, s[r]\}| = k \). Your solution must handle strings with lengths up to 10⁵ characters.

inputFormat

The input is provided via standard input (stdin) and consists of two lines:

• The first line contains a single integer k (1 ≤ k ≤ 26) representing the required number of distinct characters.
• The second line contains the string s composed of lowercase English letters. Note that s may be empty.

outputFormat

Output a single integer using standard output (stdout): the length of the longest substring of s that contains exactly k distinct characters, or -1 if no such substring exists.

2
abcba

3