A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example,
MISSISSIPPI is a shuffle of
SSISI. Let me call a string square if it is a shuffle of two identical strings. For example,
ABCABDCD is square, because it is a shuffle of
ABCD, but the string
ABCDDCBA is not square.
Is there a fast algorithm to determine whether a string is square, or is it NP-hard? The obvious dynamic programming approach doesn't seem to work.
Even the following special cases appear to be hard: (1) strings in which each character appears at most
four six times, and (2) strings with only two distinct characters. As Per Austrin points out below, the special case where each character occurs at most four times can be reduced to 2SAT.
Update: This problem has another formulation that may make a hardness proof easier.
Consider a graph G whose vertices are the integers 1 through n; identify each edge with the real interval between its endpoints. We say that two edges of G are nested if one interval properly contains the other. For example, the edges (1,5) and (2,3) are nested, but (1,3) and (5,6) are not, and (1,5) and (2,8) are not. A matching in G is non-nested if no pair of edges is nested. Is there a fast algorithm to determine whether G has a non-nested perfect matching, or is that problem NP-hard?
Unshuffling a string is equivalent to finding a non-nested perfect matching in a disjoint union of cliques (with edges between equal characters). In particular, unshuffling a binary string is equivalent to finding a non-nested perfect matching in a disjoint union of two cliques. But I don't even know if this problem is hard for general graphs, or easy for any interesting classes of graphs.
There is an easy polynomial-time algorithm to find perfect non-crossing matchings.
Update (Nov 30): I've updated the question slightly and added another bounty, now that the site has left beta and several new users are joining. New readers please note: almost all of the older answers are incorrect.