CLR cover
Previous problem

Problem 115: Greatest Fixed-Density Necklace

Next problem

A word is called a necklace if it is the lexicographically smallest word in its conjugacy class. The density of a word on the alphabet $\{\sa{0},\sa{1}\}$ is the number of occurrences of $\sa{1}$'s occurring in it. Let $N(n,d)$ be the set of all binary necklaces of length $n$ and density $d$.

The problem is concerned with the lexicographically greatest necklace in $N(n,d)$ with $0\leq d\leq n$.

The following intuitive property characterises the structure of largest necklaces.

Lemma 20

Let $C$ be the greatest necklace in $N(n,d)$:
  1. If $d\le n/2$ then $C=0^{c_0}10^{c_1}1 \cdots 0^{c_{d-1}}1$, where both $c_0\gt 0$ and, for each $i\gt 0$, $c_i\in \{c_0,c_0-1\}$.
  2. If $d\gt n/2$ then $C=01^{c_0}01^{c_1} \cdots 01^{c_{n-d-1}}$, where both $c_0\gt 0$ and, for each $i\gt 0$, $c_i\in \{c_0,c_0+1\}$.
  3. In both cases, the binary sequence $w = (0, |c_1-c_0|, |c_2-c_0|,\dots )$ is the largest necklace of its length and density.

Based on Lemma 20, design a linear-time algorithm for computing the greatest necklace in $N(n,d)$.

References

  • J. Sawada and P. Hartman. Finding the largest fixed-density necklace and Lyndon word. Inf. Process. Lett., 125:15-19, 2017.