Get Special Substring (MTS)
There are two types of characters in a particular language: special and normal. A character is special if its value is 1 and normal if its value is 0. Given string s, return the longest substring of s that contains at most k normal characters. Whether a character is normal is determined by a 26-digit bit string named charValue. Each digit in charValue corresponds to a lowercase letter in the English alphabet.
For clarity, the alphabet is aligned with charValue below:
s = "abcde"
alphabet = abcdefghijklmnopqrstuvwxyz
charValue = 10101111111111111111111111
The only normal characters in the language (according to charValue) are b and d. The string s contains both of these characters. For k = 2, the longest substring of s that contains at most k = 2 normal characters is 5 characters long, abcde, so the return value is 5. If k = 1 instead, then the possible substrings are {'b', 'd', 'ab', 'bc', 'cd', 'de', 'abc', 'cde'}. The longest substrings are 3 characters long, which would mean a return value of 3.
Complete the function getSpecialSubstring in the editor.
getSpecialSubstring has the following parameter(s):
- 1.
String s: the input string - 2.
int k: the maximum number of normal characters allowed in a substring - 3.
String charValue: a string representing special or normal value of each letter of the alphabet, ascii[a-z]
Returns
int: an integer that denotes the length of the longest substring of s with at most k normal characters
1Example 1
Align the alphabet with charValue.
abcdefghijklmnopqrstuvwxyz
01111001111111111011111111
Normal characters are in the set {a, f, g, r}. All others are special.
For the string giraffe the longest possible substrings with 2 normal characters include gir, ira and ffe.
gir: The normal characters are g and r.ira: The normal characters are r and a.ffe: The normal characters are f and f.
The maximum length substring has a length of 3.
2Example 2
In this case, there can be only 1 normal character, and all characters are normal. The maximum length of a substring can only be of length 1. The possible substrings are s, p, e, c, i, a, and l.
Constraints
Limits and guarantees your solution can rely on.
1 ≤ length of s ≤ 10^51 ≤ length of k ≤ the length of s- The length of
charValue= 26 - All values in
charValuewill be either 0 or 1