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