### egor.okhterov's blog

By egor.okhterov, history, 6 years ago,

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) = aaabbb

• If 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 :)

• +2

 » 6 years ago, # |   0 Where is this problem from?
•  » » 6 years ago, # ^ |   0 It is my problem inspired by Symbolic Sequence.For me it looks like the problem is pretty foundational, but I couldn't google neither the problem nor the solution. The closest problem that I found is the problem of assembling human genome, but again it is pretty different from what I am looking for.
•  » » » 6 years ago, # ^ |   +11 I believe this is exactly what you want.
•  » » » » 6 years ago, # ^ |   0 Thank you!But how did you google it? :)
•  » » » » » 6 years ago, # ^ |   0 I just happen to know some old problem that is named after this sequence and asks to find exactly it.
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Эхх что за времена пошли два русских друг с другом на английском общаются.UPD И у самого страна Америка )))))))
•  » » » » » » » 6 years ago, # ^ |   0 По нику не так просто понять кто есть кто =)