# PROBLEM LINK

Contest

# 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.

# SETTER'S SOLUTION

Link

asked
**15 Feb '15, 01:09**

6★sanchit_h

246●1●7

accept rate:
0%