Puzzle time - non repeating string

[jon-nyc]

Is there a finite string of letters from the Latin alphabet with the property that there is no pair of adjacent identical substrings, but the addition of any letter to either end would create one?

(Examples: In the string ABCBCA there is a pair of adjacent identical substrings, namely BC followed immediately by another BC. But the string ABCACB has no such pair.)

[Klaus]

Yes.

[Klaus]

click to show

Consider the case of an alphabet with just two letters AB.

Now consider the string ABA. It doesn't have the property.

It has four possible extensions:

AABA, BABA, ABAA, ABAB

They all have the property.

Something like that should also work for 26 letters.

[Klaus]

Here's an example that works for a 3 letter alphabet.

click to show

ABACABA

Here's one for 4 letters:

click to show

ABACABADABACABA

I think I understood the construction principle now. I refrain from executing it for 26 letters since the string would have 2^26 - 1 characters.

[Klaus]

Ah, got it now for the general case.

click to show

Let L_n be the n-th letter.

Let S_1 = L_1

Let S_(n+1) = S_n, L_(n+1), S_n

Then S_26 is the string with the desired property.

By the way, there is a well-known programming technique called hash consing with which such data which grows in size exponentially can still be represented in memory with linear space.

[jon-nyc]

That seems right to me.