The naive approach to calculate the match counts for each string would result in a
solution which would time out. By changing the order in which we process the strings, we can bring the runtime down to
We calculate the match counts in a rolling fashion. For example, for the strings
and k = 3 we proceed as follows:
abc, bcb = 0 bcb, cba = 0 - (a == b) + (b == a) = 0 cbd, bad = 0 - (b == c) + (d == d) = 1
Thus we can get the next pair of strings’ match count by subtracting the first and adding last character’s count. One such pass takes
time and we need to make two passes of complexity
to get all the substrings. The string pair’s position in the calculation is left as an exercise.