PROBLEM LINK
DIFFICULTY
Easy
SOLUTION
The naive approach to calculate the match counts for each string would result in a
O(K*N^2)
solution which would time out. By changing the order in which we process the strings, we can bring the runtime down to
O(N^2)
.
We calculate the match counts in a rolling fashion. For example, for the strings
abcbd, bcbad,
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
O(N)
time and we need to make two passes of complexity
O(N^2)
to get all the substrings. The string pair’s position in the calculation is left as an exercise.