Code Implementation

from collections import deque

class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
        def neighbors(s):
            i = 0
            while s[i] == s2[i]:
                i += 1
            for j in range(i+1, len(s)):
                if s[j] == s2[i] and s[j] != s2[j]:
                    lst = list(s)
                    lst[i], lst[j] = lst[j], lst[i]
                    yield ''.join(lst)

        queue = deque([(s1, 0)])
        visited = set([s1])
        while queue:
            state, step = queue.popleft()
            if state == s2:
                return step
            for nei in neighbors(state):
                if nei not in visited:
                    visited.add(nei)
                    queue.append((nei, step + 1))

#include <string>
#include <queue>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int kSimilarity(string s1, string s2) {
        queue<pair<string, int>> q;
        unordered_set<string> visited;
        q.push({s1, 0});
        visited.insert(s1);
        while (!q.empty()) {
            auto [curr, step] = q.front(); q.pop();
            if (curr == s2) return step;
            int i = 0;
            while (curr[i] == s2[i]) ++i;
            for (int j = i + 1; j < curr.size(); ++j) {
                if (curr[j] == s2[i] && curr[j] != s2[j]) {
                    string next = curr;
                    swap(next[i], next[j]);
                    if (!visited.count(next)) {
                        visited.insert(next);
                        q.push({next, step + 1});
                    }
                }
            }
        }
        return -1;
    }
};

import java.util.*;

class Solution {
    public int kSimilarity(String s1, String s2) {
        Queue<Pair> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(new Pair(s1, 0));
        visited.add(s1);

        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            String curr = p.str;
            int step = p.step;
            if (curr.equals(s2)) return step;
            int i = 0;
            while (curr.charAt(i) == s2.charAt(i)) i++;
            for (int j = i + 1; j < curr.length(); j++) {
                if (curr.charAt(j) == s2.charAt(i) && curr.charAt(j) != s2.charAt(j)) {
                    char[] arr = curr.toCharArray();
                    char tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
                    String next = new String(arr);
                    if (!visited.contains(next)) {
                        visited.add(next);
                        queue.offer(new Pair(next, step + 1));
                    }
                }
            }
        }
        return -1;
    }
    class Pair {
        String str;
        int step;
        Pair(String s, int k) { str = s; step = k; }
    }
}

var kSimilarity = function(s1, s2) {
    let queue = [[s1, 0]];
    let visited = new Set([s1]);
    while (queue.length) {
        let [curr, step] = queue.shift();
        if (curr === s2) return step;
        let i = 0;
        while (curr[i] === s2[i]) i++;
        for (let j = i + 1; j < curr.length; j++) {
            if (curr[j] === s2[i] && curr[j] !== s2[j]) {
                let arr = curr.split('');
                [arr[i], arr[j]] = [arr[j], arr[i]];
                let next = arr.join('');
                if (!visited.has(next)) {
                    visited.add(next);
                    queue.push([next, step + 1]);
                }
            }
        }
    }
    return -1;
};

Problem Description

You are given two strings, s1 and s2, both of which have the same length and are anagrams of each other (they contain the same characters, possibly in different orders).

You can swap any two characters in s1 that are at different positions. Your goal is to transform s1 into s2 using the smallest possible number of swaps. Each swap can involve any two positions in s1, and you may not reuse the same swap operation.

Return the minimum number of swaps needed to make s1 equal to s2.

Constraints:

• Both s1 and s2 have the same length (between 1 and 20 characters).
• Both strings consist only of lowercase letters.
• There is always at least one valid solution.
• You cannot swap a character with itself (i.e., indices must be different).

Thought Process

At first glance, the problem seems to invite a brute-force approach: try all possible swaps in s1 and see which sequence of swaps leads to s2 in the fewest moves. However, since the number of possible string permutations grows factorially with the string's length, a naive brute-force solution would be much too slow for all but the smallest inputs.

To optimize, we need to recognize that not all swaps are equally useful. A good analogy is solving a puzzle where each move should bring you closer to the goal, not just change the state randomly. So, we can think of the problem as searching for the shortest path from s1 to s2 in a graph where each node is a string, and each edge is a valid swap.

Breadth-First Search (BFS) is a natural fit for finding the shortest path in such a graph. Each level of BFS represents one swap, and we can avoid revisiting the same string multiple times using a set to track visited states. By always exploring the states closest to the goal first, we guarantee to find the minimum number of swaps.

Solution Approach

To solve the problem efficiently, we use Breadth-First Search (BFS) with some optimizations:

• Step 1: Start with the initial string s1 as the root node in our BFS queue. Each node in the queue stores the current string and the number of swaps taken to reach it.
• Step 2: For the current string, find the first index i where s1[i] != s2[i]. This is the first mismatch that needs fixing.
• Step 3: For every position j > i, if s1[j] == s2[i] and s1[j] != s2[j], swap s1[i] and s1[j]. This "fixes" the mismatch at position i and doesn't break already-matched positions.
• Step 4: For each new string generated by a swap, if it hasn't been visited before, add it to the BFS queue with an incremented swap count.
• Step 5: If at any point the current string matches s2, return the current swap count as the answer.
• Step 6: Continue until the queue is empty (which should never happen due to the problem's constraints).

Why these design choices?

• We use BFS because it guarantees the shortest path (minimum swaps) will be found first.
• We only swap with positions that help fix the current mismatch, reducing unnecessary branching.
• A visited set ensures we never process the same string twice, preventing cycles and redundant work.

Example Walkthrough

Let's walk through an example:

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

Step 1: The first mismatch is at position 0 (s1[0]='a', s2[0]='b').
We look for a 'b' in s1 after position 0. s1[1]='b' is a candidate.
Swap positions 0 and 1: "abac" → "baac"

Step 2: Next, compare "baac" to "baca".
First mismatch at position 1 ('a' vs 'a' is OK, position 2: 'a' vs 'c').
Look for 'c' in baac after position 2: s1[3]='c'.
Swap positions 2 and 3: "baac" → "baca"

Step 3: Now, "baca" matches s2. We used 2 swaps.

Result: Minimum swaps needed is 2.

Time and Space Complexity

Brute-Force Approach:

• Would explore all permutations of the string (up to n!), so time and space is O(n!). This is not feasible for even moderate n.

• Each state is a string of length n. There are at most n! unique states, but in practice, BFS with the heuristic only explores a small subset.
• The visited set and queue can grow up to O(n!) in the worst case, but are typically much smaller.
• For each state, generating neighbors takes up to O(n) time.
• Overall, time and space complexity is O(n!) in the worst case, but with the targeted swaps, it is efficient enough for n ≤ 20.

Summary

The K-Similar Strings problem asks for the minimum number of swaps needed to transform one anagram into another. By modeling the problem as a shortest-path search and using BFS with targeted swaps that always fix the earliest mismatch, we efficiently find the minimum swap count. The approach leverages the structure of the problem to avoid unnecessary computations, making it both elegant and practical for the given constraints.