# K-Similar Strings
**Difficulty:** HARD
[External](https://leetcode.com/problems/k-similar-strings)
Canonical: https://scaleengineer.com/dsa/problems/k-similar-strings
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** String
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash)
---
## 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**.

**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`.

# Approaches
## Brute-Force BFS on State Space Graph
This approach models the problem as finding the shortest path in a state space graph. Each unique permutation of the string `s1` is a node, and a single swap operation between two strings constitutes an edge. We are looking for the minimum number of edges (swaps) to get from `s1` to `s2`. Breadth-First Search (BFS) is the standard algorithm for this task. However, this brute-force method explores every possible swap at every step, leading to a combinatorial explosion of states.
**Time:** O(N! * N^2) in the worst case. We might visit all `N!` permutations, and for each, we spend `O(N^2)` time to generate neighbors. · **Space:** O(N! * N) in the worst case, to store all possible permutations in the visited set and queue. `N` is the length of the string.
**Pros:** Conceptually simple and easy to understand.; Guaranteed to find the optimal solution (the smallest `k`).
**Cons:** Extremely inefficient due to the massive state space.; The number of permutations is `N!`, and for each state, we generate `O(N^2)` neighbors.; Will result in a 'Time Limit Exceeded' error for the given constraints (`N` up to 20).
### Explanation
The algorithm starts with a queue containing the initial string `s1` and a set to store visited strings. It proceeds in levels, where each level corresponds to an additional swap. In each level, it dequeues all strings, and for each string, it generates all possible next strings by swapping every pair of characters. If a new, unvisited string is generated, it's added to the queue and the visited set. The search continues until the target string `s2` is found. The number of levels traversed gives the smallest `k`.

While correct, this approach is not feasible. For a string of length `N`, there can be up to `N!` permutations. For each permutation, we can generate `N*(N-1)/2` new strings. The complexity is prohibitive.

For example, the neighbor generation loop would look like this:
```java
char[] currentChars = currentStr.toCharArray();
for (int i = 0; i < currentStr.length(); i++) {
    for (int j = i + 1; j < currentStr.length(); j++) {
        if (currentChars[i] != currentChars[j]) {
            swap(currentChars, i, j);
            String nextStr = new String(currentChars);
            if (!visited.contains(nextStr)) {
                visited.add(nextStr);
                queue.add(nextStr);
            }
            swap(currentChars, i, j); // Backtrack
        }
    }
}
```
### Algorithm
- Model the problem as a shortest path problem on a graph.
- The nodes of the graph are all possible string permutations that can be formed from `s1`.
- An edge exists between two string nodes if one can be transformed into the other with a single swap.
- The goal is to find the shortest path from node `s1` to node `s2`.
- Use Breadth-First Search (BFS) to find this shortest path, as BFS is guaranteed to find the shortest path in an unweighted graph.
- Start a BFS from `s1`. In each step, generate all possible strings that can be obtained by swapping any two characters.
- Use a `Set` to keep track of visited strings to avoid cycles and redundant computations.
- The level of the BFS at which `s2` is found is the minimum number of swaps, `k`.

## Pruned Breadth-First Search (BFS)
We can significantly improve the brute-force BFS by being more intelligent about the swaps we explore. Instead of trying every possible swap, we only consider swaps that make concrete progress towards the target string `s2`. We identify the first position where the current string differs from `s2` and then only perform swaps that fix this specific position. This drastically prunes the search tree, making the BFS feasible for the given constraints.
**Time:** Hard to determine precisely, but it's related to `O(S * N * B)` where `S` is the number of states visited, `N` is for string operations, and `B` is the branching factor (at most `N-1`). It's significantly better than the brute-force approach. · **Space:** O(S * N), where `S` is the number of states visited and `N` is the string length. This is much smaller than `N!` but can still be large.
**Pros:** Much more efficient than the brute-force approach due to a significantly smaller search space.; Guaranteed to find the optimal solution.; It is a practical and common solution for this type of problem.
**Cons:** The worst-case time complexity can still be exponential.; Memory usage can be high if a large number of states need to be stored in the visited set and queue.
### Explanation
We use a standard BFS setup with a queue and a visited set. For each string `currentStr` we pull from the queue, we first find the first index `i` where `currentStr.charAt(i) != s2.charAt(i)`. Since `s1` and `s2` are anagrams, the character `s2.charAt(i)` must exist somewhere in `currentStr`. We then iterate from `j = i + 1` to the end of the string, looking for occurrences of `s2.charAt(i)`. Each time we find `currentStr.charAt(j) == s2.charAt(i)`, we perform the swap between `i` and `j`, create a `nextStr`, and if it's unvisited, add it to our queue and visited set. This ensures that every move makes direct progress, and since BFS explores level by level, we are guaranteed to find the path with the minimum number of swaps.

```java
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int kSimilarity(String s1, String s2) {
        if (s1.equals(s2)) {
            return 0;
        }

        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        queue.add(s1);
        visited.add(s1);

        int k = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                String currentStr = queue.poll();
                if (currentStr.equals(s2)) {
                    return k;
                }

                int firstMismatchIdx = 0;
                while (firstMismatchIdx < currentStr.length() && currentStr.charAt(firstMismatchIdx) == s2.charAt(firstMismatchIdx)) {
                    firstMismatchIdx++;
                }

                char[] currentChars = currentStr.toCharArray();
                for (int j = firstMismatchIdx + 1; j < currentStr.length(); j++) {
                    if (currentChars[j] == s2.charAt(firstMismatchIdx) && currentChars[j] != currentChars[firstMismatchIdx]) {
                        swap(currentChars, firstMismatchIdx, j);
                        String nextStr = new String(currentChars);
                        if (!visited.contains(nextStr)) {
                            visited.add(nextStr);
                            queue.add(nextStr);
                        }
                        swap(currentChars, firstMismatchIdx, j); // backtrack swap
                    }
                }
            }
            k++;
        }

        return -1; // Should not be reached
    }

    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}
```
### Algorithm
- This approach is an optimization of the brute-force BFS.
- The core idea is to reduce the branching factor of the search by only making 'useful' swaps.
- Start a BFS from `s1`.
- For any string `current_s` being processed, find the first index `i` where `current_s[i]` does not match `s2[i]`.
- A 'useful' swap is one that places the correct character, `s2[i]`, into this position `i`.
- To do this, find all indices `j > i` where `current_s[j] == s2[i]`.
- For each such `j`, generate a new string by swapping the characters at `i` and `j`.
- Add these newly generated strings to the BFS queue if they haven't been visited before.
- The number of levels in the BFS until `s2` is found is the answer.

## A* Search with Heuristic
The A* search algorithm is a powerful optimization over BFS for shortest path problems. By incorporating a heuristic function, it intelligently guides the search towards the goal. Instead of exploring all paths of a certain length equally (like BFS), A* prioritizes paths that are not only short but also appear to be getting closer to the target. This often leads to exploring far fewer states than a simple pruned BFS, making it the most efficient search-based approach for this problem.
**Time:** Worst-case complexity is similar to BFS, but the average-case performance is much better and depends on the heuristic's quality. It's difficult to give a tight bound. · **Space:** O(S * N), where `S` is the number of states visited. A* aims to make `S` as small as possible.
**Pros:** Generally the most efficient approach among search-based methods.; Significantly reduces the number of states explored compared to BFS by prioritizing promising paths.; Guaranteed to find the optimal solution because the heuristic is admissible.
**Cons:** Slightly more complex to implement than a standard BFS due to the priority queue and heuristic calculation.; The performance gain depends heavily on the quality of the heuristic.
### Explanation
We use a priority queue to store states, where each state contains the string, the number of swaps so far (`g`), and its heuristic value (`h`). The priority queue sorts states based on `g + h`. We also use a map to keep track of the minimum swaps found to reach any string, to avoid redundant explorations.

The heuristic function, `h(s)`, calculates the number of positions where `s` and `s2` have different characters, let's call this `mismatches`. The estimated swaps needed is `(mismatches + 1) / 2` (integer division for `ceil`).

The main loop extracts the state with the lowest `g + h` from the priority queue. If it's the target `s2`, we're done. Otherwise, we generate its neighbors using the same pruning strategy as before (fixing the first mismatch). For each neighbor, we calculate its new `g` and `h` values and add it to the priority queue if we've found a shorter path to it.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    class State implements Comparable<State> {
        String str;
        int g_cost; // swaps so far
        int h_cost; // heuristic estimate

        State(String str, int g, String target) {
            this.str = str;
            this.g_cost = g;
            this.h_cost = calculateHeuristic(str, target);
        }

        private int calculateHeuristic(String s1, String s2) {
            int mismatches = 0;
            for (int i = 0; i < s1.length(); i++) {
                if (s1.charAt(i) != s2.charAt(i)) {
                    mismatches++;
                }
            }
            return (mismatches + 1) / 2;
        }

        @Override
        public int compareTo(State other) {
            return (this.g_cost + this.h_cost) - (other.g_cost + other.h_cost);
        }
    }

    public int kSimilarity(String s1, String s2) {
        if (s1.equals(s2)) return 0;

        PriorityQueue<State> pq = new PriorityQueue<>();
        Map<String, Integer> minSwaps = new HashMap<>();

        pq.add(new State(s1, 0, s2));
        minSwaps.put(s1, 0);

        while (!pq.isEmpty()) {
            State current = pq.poll();

            if (current.g_cost > minSwaps.getOrDefault(current.str, Integer.MAX_VALUE)) {
                continue;
            }
            if (current.str.equals(s2)) {
                return current.g_cost;
            }

            int i = 0;
            while (current.str.charAt(i) == s2.charAt(i)) i++;

            char[] chars = current.str.toCharArray();
            for (int j = i + 1; j < chars.length; j++) {
                if (chars[j] == s2.charAt(i) && chars[j] != chars[i]) {
                    swap(chars, i, j);
                    String nextStr = new String(chars);
                    int newSwaps = current.g_cost + 1;
                    if (newSwaps < minSwaps.getOrDefault(nextStr, Integer.MAX_VALUE)) {
                        minSwaps.put(nextStr, newSwaps);
                        pq.add(new State(nextStr, newSwaps, s2));
                    }
                    swap(chars, i, j); // backtrack
                }
            }
        }
        return -1; // Should not be reached
    }

    private void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
```
### Algorithm
- This approach enhances the pruned search by using a heuristic to prioritize more promising paths, which is the core idea of the A* search algorithm.
- The search uses a priority queue instead of a regular queue.
- The priority of a state (string) is determined by `f(s) = g(s) + h(s)`.
  - `g(s)` is the actual cost (number of swaps) from the start string `s1` to the current string `s`.
  - `h(s)` is a heuristic estimate of the cost from `s` to the target `s2`.
- An effective and admissible heuristic `h(s)` is `ceil(number of mismatched positions / 2)`. This is admissible because one swap can fix at most two mismatched positions.
- The neighbor generation logic is the same as in the Pruned BFS approach.
- The algorithm terminates when it extracts `s2` from the priority queue, returning the associated `g(s2)` value.

# Solutions
### Java

```java
class Solution {
public
  int kSimilarity(String s1, String s2) {
    Deque<String> q = new ArrayDeque<>();
    Set<String> vis = new HashSet<>();
    q.offer(s1);
    vis.add(s1);
    int ans = 0;
    while (true) {
      for (int i = q.size(); i > 0; --i) {
        String s = q.pollFirst();
        if (s.equals(s2)) {
          return ans;
        }
        for (String nxt : next(s, s2)) {
          if (!vis.contains(nxt)) {
            vis.add(nxt);
            q.offer(nxt);
          }
        }
      }
      ++ans;
    }
  }
private
  List<String> next(String s, String s2) {
    int i = 0, n = s.length();
    char[] cs = s.toCharArray();
    for (; cs[i] == s2.charAt(i); ++i) {
    }
    List<String> res = new ArrayList<>();
    for (int j = i + 1; j < n; ++j) {
      if (cs[j] == s2.charAt(i) && cs[j] != s2.charAt(j)) {
        swap(cs, i, j);
        res.add(new String(cs));
        swap(cs, i, j);
      }
    }
    return res;
  }
private
  void swap(char[] cs, int i, int j) {
    char t = cs[i];
    cs[i] = cs[j];
    cs[j] = t;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int kSimilarity(string s1, string s2) {
    queue<string> q{{s1}};
    unordered_set<string> vis{{s1}};
    int ans = 0;
    while (1) {
      for (int i = q.size(); i; --i) {
        auto s = q.front();
        q.pop();
        if (s == s2) {
          return ans;
        }
        for (auto &nxt : next(s, s2)) {
          if (!vis.count(nxt)) {
            vis.insert(nxt);
            q.push(nxt);
          }
        }
      }
      ++ans;
    }
  }
  vector<string> next(string &s, string &s2) {
    int i = 0, n = s.size();
    for (; s[i] == s2[i]; ++i) {
    }
    vector<string> res;
    for (int j = i + 1; j < n; ++j) {
      if (s[j] == s2[i] && s[j] != s2[j]) {
        swap(s[i], s[j]);
        res.push_back(s);
        swap(s[i], s[j]);
      }
    }
    return res;
  }
};

```

### Python

```python
class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int: def next(s): i = 0 while s[i] == s2[i]: i += 1 res = [] for j in range(i + 1, n): if s[j] == s2[i] and s[j] != s2[j]: res . append(s2[: i + 1] + s[i + 1: j] + s[i] + s[j + 1:]) return res q = deque([s1]) vis = {s1} ans, n = 0, len(s1) while 1: for _ in range(len(q)): s = q . popleft() if s == s2: return ans for nxt in next(s): if nxt not in vis: vis . add(nxt) q . append(nxt) ans += 1

```