Problem

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.

Examples

Example 1

1
2
3

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

1
2
3

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.

Solution

Method 1 – Breadth-First Search (BFS) with Pruning

Intuition

To transform s1 into s2 with the minimum number of swaps, we can use BFS to explore all possible swaps, always swapping the first mismatched character with a character that matches s2 at that position. This ensures we only make swaps that bring s1 closer to s2, minimizing unnecessary moves.

Approach

  1. Use BFS starting from s1, keeping track of the number of swaps (steps).
  2. At each step, find the first index i where the current string differs from s2.
  3. For every j > i where current[j] == s2[i] and current[j] != s2[j], swap i and j to create a new string.
  4. Add the new string to the queue if not visited.
  5. Repeat until s1 equals s2.
  6. Return the number of swaps taken.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int kSimilarity(string s1, string s2) {
        queue<pair<string, int>> q;
        unordered_set<string> vis;
        q.push({s1, 0});
        vis.insert(s1);
        while (!q.empty()) {
            auto [cur, step] = q.front(); q.pop();
            if (cur == s2) return step;
            int i = 0;
            while (cur[i] == s2[i]) ++i;
            for (int j = i + 1; j < cur.size(); ++j) {
                if (cur[j] == s2[i] && cur[j] != s2[j]) {
                    string nxt = cur;
                    swap(nxt[i], nxt[j]);
                    if (!vis.count(nxt)) {
                        vis.insert(nxt);
                        q.push({nxt, step + 1});
                    }
                }
            }
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func kSimilarity(s1, s2 string) int {
    type pair struct{ s string; step int }
    q := []pair{{s1, 0}}
    vis := map[string]bool{s1: true}
    for len(q) > 0 {
        cur, step := q[0].s, q[0].step
        q = q[1:]
        if cur == s2 { return step }
        i := 0
        for i < len(cur) && cur[i] == s2[i] { i++ }
        for j := i + 1; j < len(cur); j++ {
            if cur[j] == s2[i] && cur[j] != s2[j] {
                nxt := []byte(cur)
                nxt[i], nxt[j] = nxt[j], nxt[i]
                ns := string(nxt)
                if !vis[ns] {
                    vis[ns] = true
                    q = append(q, pair{ns, step + 1})
                }
            }
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public int kSimilarity(String s1, String s2) {
        Queue<Pair<String, Integer>> q = new LinkedList<>();
        Set<String> vis = new HashSet<>();
        q.offer(new Pair<>(s1, 0));
        vis.add(s1);
        while (!q.isEmpty()) {
            Pair<String, Integer> p = q.poll();
            String cur = p.getKey();
            int step = p.getValue();
            if (cur.equals(s2)) return step;
            int i = 0;
            while (cur.charAt(i) == s2.charAt(i)) i++;
            for (int j = i + 1; j < cur.length(); j++) {
                if (cur.charAt(j) == s2.charAt(i) && cur.charAt(j) != s2.charAt(j)) {
                    char[] arr = cur.toCharArray();
                    char tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
                    String nxt = new String(arr);
                    if (!vis.contains(nxt)) {
                        vis.add(nxt);
                        q.offer(new Pair<>(nxt, step + 1));
                    }
                }
            }
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    fun kSimilarity(s1: String, s2: String): Int {
        data class State(val s: String, val step: Int)
        val q = ArrayDeque<State>()
        val vis = mutableSetOf<String>()
        q.add(State(s1, 0))
        vis.add(s1)
        while (q.isNotEmpty()) {
            val (cur, step) = q.removeFirst()
            if (cur == s2) return step
            var i = 0
            while (cur[i] == s2[i]) i++
            for (j in i+1 until cur.length) {
                if (cur[j] == s2[i] && cur[j] != s2[j]) {
                    val arr = cur.toCharArray()
                    arr[i] = arr[j].also { arr[j] = arr[i] }
                    val nxt = String(arr)
                    if (nxt !in vis) {
                        vis.add(nxt)
                        q.add(State(nxt, step + 1))
                    }
                }
            }
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
        from collections import deque
        q = deque([(s1, 0)])
        vis = {s1}
        while q:
            cur, step = q.popleft()
            if cur == s2:
                return step
            i = 0
            while cur[i] == s2[i]:
                i += 1
            for j in range(i+1, len(cur)):
                if cur[j] == s2[i] and cur[j] != s2[j]:
                    nxt = list(cur)
                    nxt[i], nxt[j] = nxt[j], nxt[i]
                    nxt_str = ''.join(nxt)
                    if nxt_str not in vis:
                        vis.add(nxt_str)
                        q.append((nxt_str, step+1))
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

use std::collections::{HashSet, VecDeque};
impl Solution {
    pub fn k_similarity(s1: String, s2: String) -> i32 {
        let mut q = VecDeque::new();
        let mut vis = HashSet::new();
        q.push_back((s1.clone(), 0));
        vis.insert(s1.clone());
        while let Some((cur, step)) = q.pop_front() {
            if cur == s2 { return step; }
            let cur_bytes = cur.as_bytes();
            let s2_bytes = s2.as_bytes();
            let mut i = 0;
            while cur_bytes[i] == s2_bytes[i] { i += 1; }
            for j in i+1..cur.len() {
                if cur_bytes[j] == s2_bytes[i] && cur_bytes[j] != s2_bytes[j] {
                    let mut nxt = cur_bytes.to_vec();
                    nxt.swap(i, j);
                    let nxt_str = String::from_utf8(nxt).unwrap();
                    if !vis.contains(&nxt_str) {
                        vis.insert(nxt_str.clone());
                        q.push_back((nxt_str, step+1));
                    }
                }
            }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    kSimilarity(s1: string, s2: string): number {
        const q: [string, number][] = [[s1, 0]];
        const vis = new Set<string>([s1]);
        while (q.length) {
            const [cur, step] = q.shift()!;
            if (cur === s2) return step;
            let i = 0;
            while (cur[i] === s2[i]) i++;
            for (let j = i + 1; j < cur.length; ++j) {
                if (cur[j] === s2[i] && cur[j] !== s2[j]) {
                    const arr = cur.split('');
                    [arr[i], arr[j]] = [arr[j], arr[i]];
                    const nxt = arr.join('');
                    if (!vis.has(nxt)) {
                        vis.add(nxt);
                        q.push([nxt, step + 1]);
                    }
                }
            }
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(n! * n), where n is the length of the string. In the worst case, we may explore all permutations, but pruning reduces the search space.
  • 🧺 Space complexity: O(n! * n), for the queue and visited set.