854. K-Similar Strings

Description

Strings s1 and s2 are k-similar (for some non-negative integer k) if we can swap the positions of two letters in s1 exactly k times so that the resulting string equals s2.

Given two anagrams s1 and s2, return the smallest k for which s1 and s2 are k-similar.

 

Example 1:

Input: s1 = "ab", s2 = "ba"
Output: 1
Explanation: The two string are 1-similar because we can use one swap to change s1 to s2: "ab" --> "ba".

Example 2:

Input: s1 = "abc", s2 = "bca"
Output: 2
Explanation: The two strings are 2-similar because we can use two swaps to change s1 to s2: "abc" --> "bac" --> "bca".

 

Constraints:

• 1 <= s1.length <= 20
• s2.length == s1.length
• s1 and s2 contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}.
• s2 is an anagram of s1.

 

Solutions

Solution: Breadth-First Search

• Time complexity: O(n²k)
• Space complexity: O(n²)

 

JavaScript

/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
const kSimilarity = function (s1, s2) {
  if (s1 === s2) return 0;
  const n = s1.length;
  const visited = new Set([s1]);
  let queue = [s1];
  let result = 0;

  while (queue.length) {
    const nextQueue = [];

    for (const word of queue) {
      let a = 0;

      while (a < n && word[a] === s2[a]) a += 1;

      for (let b = a + 1; b < n; b++) {
        if (word[b] === s2[b]) continue;
        if (word[a] !== s2[b]) continue;
        const startWord = word.slice(0, a);
        const middleWord = word.slice(a + 1, b);
        const endWord = word.slice(b + 1);
        const nextWord = `${startWord}${word[b]}${middleWord}${word[a]}${endWord}`;

        if (nextWord === s2) return result + 1;
        if (visited.has(nextWord)) continue;
        visited.add(nextWord);
        nextQueue.push(nextWord);
      }
    }
    queue = nextQueue;
    result += 1;
  }
  return -1;
};