Unshuffling a square is NP-hard
The problem of recognizing a square shuffle is NP-complete. It remains complete over finite alphabets of size 7. The proof is based on a many-one reduction from 3-Partition.
square shuffle np-completeness