In this problem, we'll use the term "longest common substring" loosely. It refers to substrings differing at some number or fewer characters when compared index by index. For example, 'abc' and 'adc' differ in one position, 'aab' and 'aba' differ in two.
Given two strings and an integer , determine the length of the longest common substrings of the two strings that differ in no more than positions.
For example, . Strings and . Check to see if the whole string (the longest substrings) matches. Given that neither the first nor last characters match and , we need to try shorter substrings. The next longest substrings are and . Two pairs of these substrings only differ in position: and . They are of length .
Complete the substringDiff function in the editor below. It should return an integer that represents the length of the longest common substring as defined.
substringDiff has the following parameter(s):
k: an integer that represents the maximum number of differing characters in a matching pair
s1: the first string
s2: the second string
The first line of input contains a single integer, , the number of test cases follow.
Each of the next lines contains three space-separated values: an integer and two strings, and .
All characters in and .
For each test case, output a single integer which is the length of the maximum length common substrings differing at or fewer positions.