×

Contest

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

This question is marked "community wiki".

24617
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,875
×3,828
×355
×7
×1

question asked: 15 Feb '15, 01:09

question was seen: 705 times

last updated: 15 Feb '15, 01:09