Problem statement

Two strings are k-similar if you can turn the first into the second by swapping the positions of two letters exactly k times.

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

Example 1

Input: s1 = "ab", s2 = "ba"
Output: 1

Example 2

Input: s1 = "abc", s2 = "bca"
Output: 2
Explanation: "abc" → "bac" → "bca".

Example 3

Input: s1 = "abac", s2 = "baca"
Output: 2

Constraints

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

Hints for K-Similar Strings

1. Hint 1

   Think of each string as a state and each swap as an edge: the answer is a shortest path, so BFS from s1.

2. Hint 2

   Trying all n^2 swaps per state explodes. Positions that already match s2 never need to move, so always work on the first mismatched index i.

3. Hint 3

   Only swap i with a later j where s[j] == s2[i] (that fixes position i) and s[j] != s2[j] (never break a position that is already right).

How to solve K-Similar Strings

Breadth-first search over strings, where each level is one swap. The branching is cut down by always fixing the first position that differs from s2, using only swaps that put the right letter there and take it from a position that was itself wrong.

Approach

1. If s1 == s2, return 0. Otherwise push s1 into a queue and a visited set.
2. Process the queue level by level, counting levels as swaps.
3. For a string s, find the first index i with s[i] != s2[i]. For each j > i with s[j] == s2[i] and s[j] != s2[j], swap i and j.
4. If the new string equals s2, return the current level; otherwise enqueue it if unseen.

Why it works

Some optimal sequence of swaps fixes position i in its first swap that touches i, and swaps commute enough that we may perform that one first. That swap must bring the letter s2[i] from some j; taking it from a position that is already correct would cost an extra swap to repair, so only mismatched j need to be tried. Hence the pruned search still contains an optimal path, and BFS finds the shortest.

Complexity

• Time — O(n^2 · S) where S is the number of states explored — small in practice for n ≤ 20 over six letters
• Space — O(n · S)

Pitfalls

• Always branch on the first mismatch only — branching on every mismatch multiplies the state space with no benefit.
• Count levels, not individual dequeues.
• A swap of two equal letters changes nothing; the s[j] != s2[j] filter also prevents useless moves.

Reference solution

Python

from collections import deque

def kSimilarity(s1: str, s2: str) -> int:
    if s1 == s2:
        return 0
    n = len(s1)
    seen = {s1}
    q = deque([s1])
    d = 0
    while q:
        d += 1
        for _ in range(len(q)):
            s = q.popleft()
            i = 0
            while s[i] == s2[i]:
                i += 1
            for j in range(i + 1, n):
                if s[j] == s2[i] and s[j] != s2[j]:
                    t = s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:]
                    if t == s2:
                        return d
                    if t not in seen:
                        seen.add(t)
                        q.append(t)
    return d

Java

public static int kSimilarity(String s1, String s2) {
    if (s1.equals(s2)) return 0;
    int n = s1.length(), d = 0;
    Set<String> seen = new HashSet<>();
    ArrayDeque<String> q = new ArrayDeque<>();
    seen.add(s1);
    q.add(s1);
    while (!q.isEmpty()) {
        d++;
        for (int size = q.size(); size > 0; size--) {
            char[] s = q.poll().toCharArray();
            int i = 0;
            while (s[i] == s2.charAt(i)) i++;
            for (int j = i + 1; j < n; j++) {
                if (s[j] != s2.charAt(i) || s[j] == s2.charAt(j)) continue;
                char tmp = s[i]; s[i] = s[j]; s[j] = tmp;
                String t = new String(s);
                if (t.equals(s2)) return d;
                if (seen.add(t)) q.add(t);
                tmp = s[i]; s[i] = s[j]; s[j] = tmp;
            }
        }
    }
    return d;
}

C++

int kSimilarity(string s1, string s2) {
    if (s1 == s2) return 0;
    int n = s1.size(), d = 0;
    unordered_set<string> seen{s1};
    queue<string> q;
    q.push(s1);
    while (!q.empty()) {
        d++;
        for (int size = q.size(); size > 0; size--) {
            string s = q.front(); q.pop();
            int i = 0;
            while (s[i] == s2[i]) i++;
            for (int j = i + 1; j < n; j++) {
                if (s[j] != s2[i] || s[j] == s2[j]) continue;
                swap(s[i], s[j]);
                if (s == s2) return d;
                if (seen.insert(s).second) q.push(s);
                swap(s[i], s[j]);
            }
        }
    }
    return d;
}

JavaScript

var kSimilarity = function(s1, s2) {
    if (s1 === s2) return 0;
    var n = s1.length, seen = {}, q = [s1], d = 0;
    seen[s1] = true;
    var head = 0;
    while (head < q.length) {
        d++;
        var end = q.length;
        for (; head < end; head++) {
            var s = q[head], i = 0;
            while (s[i] === s2[i]) i++;
            for (var j = i + 1; j < n; j++) {
                if (s[j] !== s2[i] || s[j] === s2[j]) continue;
                var t = s.substring(0, i) + s[j] + s.substring(i + 1, j) + s[i] + s.substring(j + 1);
                if (t === s2) return d;
                if (!seen[t]) { seen[t] = true; q.push(t); }
            }
        }
    }
    return d;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Prefix and Suffix Search Hard
• Recover a Tree From Preorder Traversal Hard
• Minimum Time to Revert Word to Initial State II Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• Find the Original Typed String II Hard