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.