CLR cover

Additional Problem 18: Grasshopper avoidance of repetitions

\( \)

For a string $w$ its grasshopper subsequence is any subword of the form $w[i_1]w[i_2]\cdots w[i_k]$, where $i_{t+1}\in \{i_t+1,i_t+2\}$ for each $t\lt k$. We can imagine a grasshopper jumping to the right one or two positions and avoiding repetitions.

Define a grasshopper square/grasshopper cube of a string a grasshopper subsequence which is a square/cube.

Let $A=\{a,b,c\}$ and $A'=\{a',b',c'\}$. The elements of $A'$ are called primed. Assume $v$ is over the alphabet $A$. We create the word $\code(w)$ over the alphabet $A\cup A'$ using the coding: $$a \rightarrow aa',\; b \rightarrow bb',\; c \rightarrow cc'$$

Assume $y=\code(x)$ and $z$ is a grasshopper square in $y$. Compute in time $O(|z|)$ a square $v$ in $x$ of size at least $|z|/2$.

For a given number $n$ and a 6-letter alphabet construct a string $w$ of length $n$ over this 6-letter alphabet avoiding grasshopper squares.

For a given number $n$ and a 3-letter alphabet construct a string $w$ of length $n$ over this 3-letter alphabet avoiding grasshopper cubes.

References