0

Given a text T and a set of strings S (where the combined length of strings in S equals the length of T), find the most efficient sequence of swaps to apply to T so that all of the substrings in S appear exactly in T, where non-adjacent swaps are allowed. The characters in T will always be unique and will always have a corresponding character in S.

For example:

T = "ABCDE"

S = {"CB", "EDA"}

the desired resulting string could be either "CBEDA" or "EDACB" (whichever can be achieved with fewer swaps). One way to solve this case would be:

"ABCDE". swap A and C: "CBADE". swap A and E: "CBEDA".

Wiktor Stribiżew
  • 561,645
  • 34
  • 376
  • 476
jamman2000
  • 15
  • 4
  • Makes me think of a variation of https://en.wikipedia.org/wiki/Levenshtein_distance Have also a look here : https://stackoverflow.com/questions/15152322/compute-the-minimal-number-of-swaps-to-order-a-sequence – Jean Valj Jan 30 '22 at 18:07

0 Answers0