Blanwhit
Blanwhit
PostsComments
KPCKevin Powell - Community
Created by Blanwhit on 12/26/2024 in #back-end
How to get from string to anagram in fewest number of swaps?
I'm using Python for the backend of this project. I have a string l1 that is 19 characters long. I have a string l2 that is an anagram of l1 (l2 has the same characters as l1 but shuffled). I want to get from l1 to l2 in the fewest number of steps, the only move allowed is to swap any two letters (they don't have to be adjacent). l1 can have repeated letters. I'm trying to create a function that outputs the swaps the user needs to make to achieve the least possible number, represented as tuples with the indices of the letters the user needs to swap. For example, 
l1 = "abc123456789abcdefg"
l2 = "cca123456789bbadefg"

# f(l1, l2) should return:
# [(0, 14), (1, 12), (1, 3)]
l1 = "abc123456789abcdefg"
l2 = "cca123456789bbadefg"

# f(l1, l2) should return:
# [(0, 14), (1, 12), (1, 3)]
I've tried BFS, but I couldn't figure out a way to make it work with repeated letters. It seems quite straightforward, but I can't figure out a way to ensure minimum swaps. Any help would be appreciated.
14 replies