learner_321's blog

By learner_321, history, 4 months ago, In English,

You are given to Strings , in one String you can swap any adjacent character , also you can swap first and last character . Find the minimum number of swaps required to make two String similar.

Sample Ip —

S1- aab S2- baa

Op — 1

You can swap first and last character of S2 , so ans will be 1.

How to solve this ?

Constraints were 1<=|S1|, |S2| <= 2000.

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

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone please help ?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I want to help, but seems like I can't find a solution myself. So I just upvoted your post. Haha.

    All those upvotes on your post probably means, "Good question Mate. I want to know the solution too!"

    Don't reply to my comment right now. Wait till the post drowns down in few days. Comment then and it will pop up again at top. Keep repeating this until some smart person comments the solution :p

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

is greedy algo correct?

enum the first target postion move the charater to this postion there are two candidate characters left nearest char and right nearest char just enum it..

after fix the first target postion ,just move need character to the second adjcent postion to the first,any direction is ok, move the nearest char to this. process until end...