I'm trying to solve the following problem:
Two strings can be shuffled by interleaving their letters to form a new string (original order of letters is preserved). We will consider a shuffle of two identical strings (twins).
For instance, the string AAABAB can be obtained by shuffling two strings AAB.
For a given string we should check if it can be obtained by shuffling two twins.
At first, we should check the parity of each letter (XOR of all letters == 0).
Next, i can't think up anything except brute-force solution with complexity O(2^N) :(
Is there a way to solve the problem efficiently? Thanks!