K-Similar Strings

HardGraphsbfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given two strings s1 and s2 that are anagrams of each other. In one move you may pick two positions of s1 and exchange the characters there. Return the **smallest** number of moves needed to turn s1 into s2. If the strings are already equal, the answer is 0. Strings are short (at most 20 characters) but the number of arrangements grows factorially, so search the state space carefully.

Examples

Input: s1 = "ab", s2 = "ba"
Output: 1
One swap of the two characters is enough.
Input: s1 = "abc", s2 = "bca"
Output: 2
"abc" -> "bac" -> "bca".

Constraints

  • 1 <= s1.length <= 20
  • s2.length == s1.length
  • s1 and s2 contain only the letters 'a' through 'f'
  • s2 is an anagram of s1

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bfs problems