You are given a string S containing only lowercase letters and an integer K. In one operation you can change any character of the string to '#' character.

Note: '#' is not considered when checking for duplicates.

Task

Print the minimum number of operations required such that no substring of size K contains duplicates.

Example

Assumptions

S = "ababc"
K = 3

Approach

Here, in the substrings "aba" & "bab", you encounter duplicates.
Replace the first 2 characters with '#' and the final string becomes "##abc"
Therefore the answer is 2.

Function description

Complete the solve function provided in the editor. This function takes the following 2 parameters and returns an integer that represents the answer to the task as described in the problem statement:

S: Represents the string
K: Represents the size of the substring

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

The first line contains the function parameter S.
The second line contains the function parameter K.

Output format

Print an integer representing the answer to the given task.

Constraints

\(1 \leq |S| \leq 1*10^5\)

\(1 \leq K \leq min(|S|,26)\)

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.