Last Updated: 29 Sep, 2025
Longest Normal-Character Substring
Moderate
Asked in company
You are given a string S of N lowercase English letters. Each letter of the alphabet ('a' through 'z') is classified as either normal or special. You are also given an integer K.
Your task is to find the length of the longest substring of S that contains at most K normal characters.
Input Format:
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.
Output Format:
Print a single integer representing the length of the longest valid substring.
Note:
A naive solution of checking every possible substring would be too slow (O(N^2)).
