[Python] Python code needed to extract an unknown string after it's been randomly shuffled...

By shuffling I mean that two source strings are merged together into a third string, and the order of the characters in the two source strings remain the same, but they may be interspersed with a random number of characters from the other source string. The analogy is shuffling a deck of cards, where the order of the cards in each half-deck is unchanged by the shuffle, but the two half-decks are randomly interspersed between each other.

Example merged string: "UDpigsitidael P Paayrmticeipnattion 1x (6U0n%capped)"

Example known string: "Upside Participation 1x (Uncapped)"

Example unknown string: "Digital Payment 60%".

I have tried a simple greedy algorithm that matches each character of the known string, in order, with the earliest next occurrence in the merged string, but it can fail when characters are duplicated. I think a backtracking algorithm is needed.

Continue reading...