Sign In

Communications of the ACM

Last byte

String Me Along


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
colorful letters of the alphabet

Credit: Getty Images

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.

uf1.jpg
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
Article Contents:
  • Article
  • Author
  • Footnotes
  • ACM Resources