Longest Normal-Character Substring

The first line contains two space-separated integers, N and K.

The second line contains the string S of length N.

The third line contains a 26-character string, char_types, representing the types for 'a' through 'z' respectively. 'N' denotes a normal character, and 'S' denotes a special character.

Print a single integer representing the length of the longest valid substring.

A naive solution of checking every possible substring would be too slow (O(N^2)).

Sample Input 1:

10 3
abcspeciala
NNSSNSSSSSSSSSSSSSSSSSSSSSS

Sample Output 1:

4

Explanation for Sample 1:

- Normal characters are 'a', 'b', 'e'. `K=3`.
- String: `abcspeciala`
- The sliding window expands until it hits `abcspeci**a**la`.   The substring is `[abcspecia]`. It contains the normal characters `a, b, e, a`. There are 4 normal characters, which is `> K`.
- The window must shrink from the left. The `a` at the start is removed. The window is now `[bcspecia]`. It contains normal characters `b, e, a`. There are 3, which is `<= K`. This is a valid window.
- Its length is 8. This is the maximum length found.

Sample Input 2:

13 0
specialstring
NNNNNNNNNNNNNNNNNNNNNNNNNN

Sample Output 2:

0

Explanation for Sample 2:

All characters are normal. We are allowed `K=0` normal characters. The only substring that satisfies this is an empty one. The longest length is 0.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= N <= 10^5
0 <= K <= N
`S` consists of lowercase English letters.
`char_types` has a length of 26.