Identical Letters

Interview

Time limit2sMemory limit1024 MB

Summary

Given a lowercase string and an integer m, find the longest run of one repeated letter you can form by deleting at most m letters.

Level: Medium4 of 10
Topics: Sliding window, String, Two pointers
Solved: No attempts yet

Problem

Computer scientists are always interested in streaks of identical letters, so they look for the longest consecutive run of the same letter in a string.

Given a string $S$ of lowercase letters and an integer $m$ , find the maximum number of consecutive identical letters in $S$ when you remove up to $m$ letters from the string. You do not have to remove exactly $m$ letters.

Input

The first line contains the string $S$ , which contains only lowercase letters. Its length is at least $1$ and at most $2 \times 10^5$ .

The second line contains an integer $m$ ( $0 \le m \le |S|$ ), the maximum number of letters you can remove.

Output

Print the maximum number of consecutive identical letters that you can get after removing up to $m$ letters from the string.

Hint

For the first sample, you can remove the two letters at positions 10 and 11.

For the second sample, you can remove the letters at positions 3, 4, 6, 10, and 11.

For the third sample, you can create a run of two a's or two y's, so the answer is 2.

Examples3

Example 1
Input
```
bbazbcbbbcybbx
2
```
Expected output
```
5
```
Example 2
Input
```
bbazbcbbbcybbx
5
```
Expected output
```
8
```
Example 3
Input
```
zabcadyhxwuy
5
```
Expected output
```
2
```