igor.pisarev's blog

"Twin strings" problem
By igor.pisarev, 11 years 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

»
11 years 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.

→ Reply
  • »
    »
    11 years 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"

    → Reply
    • »
      »
      »
      11 years 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.

      → Reply
»
11 years 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

→ Reply