Use dynamic Programming. This is just a variation of the MCM problem and can be understood just by building a recursion tree as we generally do for MCM-type problems. It is a standard problem, just we need to identify the pattern.

The idea is to maintain a maxHeap of size k. A number is to be evicted from this heap if the k-sized window moves past it.
-> If that number to be evicted is at the top, immediately pop the heap.
-> if not, then maintain a toDelete heap which will evict the number as soon as it reaches top in both. Keep discarding numbers from both these heaps until the tops don't match.

For every string s we pre-calculate the length of the longest possible overlap between s and any other strings. 

Then for every possible subset A'of A, we could use the sum of the precalculated lengths as an upper bound to the total overlaps that can be obtained by combining all the strings in A'. 

Using this upper bound, we could give up early on many branches.