We have all the possible 3-grams of lower case letters (A = {a, b, c, ..., z}):
A3 = A × A × A =
{
(a, a, a),
(a, a, b),
(a, a, c),
...,
(a, a, z),
(b, a, a),
...,
(z, z, y),
(z, z, z),
}
|A3| = 263 = 17576
If we try to merge aaa with bbb we have to append bbb to the end of aaa, because they don't overlap:
merge(aaa, bbb) = aaabbbIf we merge aaa with aab we can create a smaller string:
merge(aaa, aab) = aaab
In the best case, if we manage to always do a second kind of merge, we will be extending the resulting string by 1 character. There are 17576 triplets, so there can be at most 17575 single character extensions. This will result in 17575 + 3 = 17578 characters string.
In the worst case, we will append all of the 3-grams to each other, thus creating a 17576 * 3 = 52728 characters string.
How to combine all of them to get the total string of the minimum length?
Picture to attract people :)