Hello!
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!
Note that the first letter of the given string also has to be the first letter of each twin. We can remove the first two copies of that letter, and then recurse. This should give an O(n) algorithm if implemented efficiently.
Edit: it appears this problem is NP-hard. My solution is wrong.
I've posted similar solution to the russian branch. But if I understand you correctly, your solution fails on the test "ABCCAB". Answer for this test is "no"
No, maybe I didn't explain my solution well enough. Here is pseudocode of my idea:
edit: fixed a bug in pseudocode
edit: I'm wrong, sorry.
You won't be able to solve this problem efficiently, unless P=NP. Link
Thank you for the link. Haven't found it, very interesting