Sign In

# Communications of the ACM

Last byte

## String Me Along

Consider the following solitaire or multiperson game that will be called "String Me Along." You are given a collection of k distinct letters, for example, A, B, C, and a number j. A well-formed string has no repeats of any substrings of length j. Such repeats would be called j-repeats.

For example, A B C A C C A B has a two-repeat of A B, but

A B C A C C B A has no two-repeat.

If the string is free of j-repetitions, but adding any letter from the collection would cause a j-repetition, the string is said to be j-complete.

For example, let's say that j = 2 and the collection is A, B, C. Here is a two-complete string.

A A B B C C B A C A

It is not possible to extend this further because A has already been followed by A, B, and C.

Warm-Up: The two-complete string above for A, B, and C was of length 10. Is it possible to get a shorter two-complete string for A, B, and C?

Solution to Warm-Up: Here is one example: A B B A C C A A.

Question: What is the length of the shortest two-complete string on A, B, C?

Solution: The shortest length is six. Here is an example: A A B A C A. As in the example, it is not possible to extend this further because A has already been followed by A, B, and C. Further, any two-complete string in which it is impossible to follow A must both end with an A and must include A B, A C, as well as A A so cannot be shorter than 6.

End of Solution to Warm-Up.

A larger j gives more possibilities, so the shortest possible string could get longer. But how much longer?

Challenge: Find a three-complete string on A, B, C of length 11 or less.

Figure. A two-complete string is one in which no two-letter subsequence is present more than once, but appending any letter would violate that condition. Would adding the A make this string two-complete?

Solution: Here is one of length 11.

A B C A B B A B A A B

The reason this is complete is that A B has already been followed by C, B, and A. Note that you might think, based on the same reasoning, that

A B C A B B A B A B

is three-complete, but it is not because B A B appears twice so it has a three-repetition already.

This last challenge suggests a game in which players alternate adding letters to the string without causing j-repetitions. If some player cannot do so, then that player loses.

Challenge: Suppose that in some game, the string so far is

A B C A A C

It is the Player 1's move now. Can either player force the other to cause a two-repetition?

Solution: Player 1 should not append A next because C A is already present. Player 1 could append B or C, but appending B would be foolish because then Player 2 could put in A next and then Player 1 would not be able to continue. So, Player 1 puts in C, yielding

A B C A A C C

This forces Player 2 to append B allowing Player 1 to append A, yielding

A B C A A C C B A

Player 2 cannot extend this further, so Player 1 wins.

You are ready for the upstarts.

Upstart 1: Is there a three-complete string on A, B, and C of length 10 or less?

Upstart 2: Given k letters and some j, what is the longest j-complete string one can get and what is the shortest?

Upstart 3: Is there a forced winning strategy for either player for j = 2 for k >= 2 letters?

Upstart 4: Is there a forced winning strategy for general j and k?

Back to Top

### Author

Dennis Shasha (dennisshasha@yahoo.com) is a professor of computer science in the Computer Science Department of the Courant Institute at New York University, New York, NY, USA, as well as the chronicler of his good friend the omniheurist Dr. Ecco.

Back to Top

### Footnotes

All are invited to submit their solutions to upstartpuzzles@cacm.acm.org; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html

Copyright held by author.
Request permission to (re)publish from the owner/author

The Digital Library is published by the Association for Computing Machinery. Copyright © 2021 ACM, Inc.

No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account