igor.pisarev's blog

By igor.pisarev16 months ago, translation, In English,

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!

 
 
 
 
  • Vote: I like it  
  • +20
  • Vote: I do not like it  

 
»
16 months ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

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.

  •  
    »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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"

    •  
      »
      »
      »
      16 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      No, maybe I didn't explain my solution well enough. Here is pseudocode of my idea:

      def is_twin_shuffle(string g of length n):
        s = ""
        t = ""
        s_index = 0
        for i from 0 to n-1:
          if s_index = length of s or g[i] != s[s_index]:
            s += g[i]
            if s_index == -1:
              s_index = 0
          else:
            t += g[i]
            s_index += 1
        return (s == t)
      

      edit: fixed a bug in pseudocode

      edit: I'm wrong, sorry.

 
»
16 months ago, # |
  Vote: I like it +24 Vote: I do not like it

You won't be able to solve this problem efficiently, unless P=NP. Link

  •  
    »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for the link. Haven't found it, very interesting