K-Similar Strings

hard bfs string graph

Problem

Given two anagrams s1 and s2 of equal length, return the smallest k such that you can transform s1 to s2 by k swaps of two characters.

Inputs1 = "ab", s2 = "ba"

Output1

One swap suffices.

input

from collections import deque

def kSimilarity(s1, s2):
    seen = {s1}
    q = deque([(s1, 0)])
    while q:
        cur, k = q.popleft()
        if cur == s2: return k
        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 = cur[:i] + cur[j] + cur[i + 1:j] + cur[i] + cur[j + 1:]
                if nxt not in seen:
                    seen.add(nxt)
                    q.append((nxt, k + 1))

function kSimilarity(s1, s2) {
  const seen = new Set([s1]);
  const q = [[s1, 0]];
  while (q.length) {
    const [cur, k] = q.shift();
    if (cur === s2) return k;
    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 (!seen.has(nxt)) { seen.add(nxt); q.push([nxt, k + 1]); }
      }
    }
  }
}

import java.util.*;
class Solution {
  public int kSimilarity(String s1, String s2) {
    Set<String> seen = new HashSet<>();
    Queue<String> q = new ArrayDeque<>();
    q.offer(s1); seen.add(s1);
    int k = 0;
    while (!q.isEmpty()) {
      for (int sz = q.size(); sz > 0; sz--) {
        String cur = q.poll();
        if (cur.equals(s2)) return k;
        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[] a = cur.toCharArray();
            char t = a[i]; a[i] = a[j]; a[j] = t;
            String nxt = new String(a);
            if (seen.add(nxt)) q.offer(nxt);
          }
        }
      }
      k++;
    }
    return -1;
  }
}

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int kSimilarity(string s1, string s2) {
        unordered_set<string> seen{s1};
        queue<string> q; q.push(s1);
        int k = 0;
        while (!q.empty()) {
            for (int sz = q.size(); sz > 0; sz--) {
                string cur = q.front(); q.pop();
                if (cur == s2) return k;
                int i = 0;
                while (cur[i] == s2[i]) i++;
                for (int j = i + 1; j < (int)cur.size(); j++) {
                    if (cur[j] == s2[i] && cur[j] != s2[j]) {
                        string nxt = cur;
                        swap(nxt[i], nxt[j]);
                        if (!seen.count(nxt)) { seen.insert(nxt); q.push(nxt); }
                    }
                }
            }
            k++;
        }
        return -1;
    }
};

Explanation

We want the fewest swaps to turn s1 into s2. Treat each possible string as a node in a graph, with an edge for every single swap; then "fewest swaps" is just the shortest path, which BFS finds level by level.

The smart part is keeping the branching small. From the current string we find the first index i that does not match s2, and we only consider swaps that put the correct character into that spot. So for each later index j where cur[j] == s2[i] (and j is itself misplaced), we swap i and j — every such move fixes position i, so no swap is ever wasted.

A seen set stops us from revisiting strings, and the BFS depth k counts swaps. The first time we dequeue a string equal to s2, that depth is the minimum, so we return it.

Example: s1 = "ab", s2 = "ba". The first mismatch is index 0 (we have a, need b); index 1 holds b, so swapping 0 and 1 yields "ba" at depth 1. Answer: 1.

Because each level only branches on character-fixing swaps, BFS reaches the target with the smallest possible swap count.

Time: exponential worst-case Space: O(states)