MAXIMUM STRING FOLDING

• INSTANCE: Finite alphabet $\Sigma$, finite string s from $\Sigma^*$.

• SOLUTION: A folding of s in the 3-dimensional rectangular grid $Z^3$, that is, a mapping of s into $Z^3$ such that adjacent symbols of s are adjacent in the lattice, and no site in the lattice is occupied by more than one symbol.

• MEASURE: The number of pairs of equal symbols that lie at adjacent lattice sites (excluding pairs that are adjacent in s).

  
  

• Bad News: APX-hard under randomized polynomial time reductions [385].