Hello Everyone,

I gave my Amazon SDE2 interview yesterday.
Due to NDA I actually didn't want to give out any information and it is no different than the interview experiences that are posted here.

But I was asked below question in one of my coding interviews and I had no clue how to solve it. Even though I am pretty much accustomed of solving medium level questions in 30 minutes after around 300 Leetcode problems.
Here is the question, Please comment if you find a decent logic to go around it.

https://leetcode.com/problems/k-similar-strings/
Given two strings which are anagrams of each other, you can swap characters from any one string to make it identical to another. Return the minimum number of swaps.

E.g S1 = abc, S2 = bac Swaps = 1: Pretty simple test case.

S1 = aabcdeer S2= aebcedra Swaps = 3

I did ask what could be the max length of these strings to which interviewer said 100
I approached this one with making graph like structure but didn't exactly know what logic will return minmum swaps. Like you can find largest cycle and it requires cycle length - 1 swaps. But if there is atleast one character that is misplaced twice it becomes more difficult to find that largest cycle. And given that String length could be 100, you never know the possibilities, I tried to search this online a lot, where I found out that it becomes a NP hard problem in this case.