Maximum Distinct Colors in a Necklace

You are given a string beads representing a sequence of beads, where each character indicates the color of a bead, and an integer length that specifies the number of contiguous beads to be examined. Your task is to determine the maximum number of distinct colors present in any contiguous substring of beads with exactly length characters.

For example, if the beads are represented by "abcabcabc" and the length is 3, then every substring of size 3 (such as "abc", "bca", "cab", etc.) has 3 distinct colors, so the answer is 3. Similarly, if the beads are "aabbcc" with a length of 2, the answer is 2 because the maximum distinct colors in any contiguous substring of length 2 is 2.

Note: The distinct count for a window is computed by the number of unique characters within that window.

The sliding window solution should work in O(N) where N is the length of the string.

The mathematical essence for the calculation can be described in LaTeX as follows:

$$\text{maxDistinct} = \max_{0 \le i \le n - L} \left|\{ \text{beads}[i], \text{beads}[i+1], \dots, \text{beads}[i+L-1] \}\right|$$

inputFormat

The input is given in two lines:

• The first line contains a non-empty string beads representing the beads sequence.
• The second line contains an integer length (L) which indicates the size of the contiguous segment.

outputFormat

Output a single integer, which is the maximum number of distinct colors in any contiguous substring of length length taken from beads.

## sample

abcabcabc
3

3