相似度为 K 的字符串

/*
 * Problem: Given two anagrams s1 and s2, return the minimum number of swaps required to make s1 equal to s2.
 * Solution: This solution also uses BFS but utilizes Java Streams for some operations.
 */

import java.util.*;
import java.util.stream.Collectors;

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

        int n = s1.length();
        Queue<State> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        queue.add(new State(s1, 0));
        visited.add(s1);

        while (!queue.isEmpty()) {
            State current = queue.poll();
            List<Integer> mismatches = current.str.chars()
                .filter(c -> c != s2.charAt(current.str.indexOf((char)c)))
                .boxed()
                .collect(Collectors.toList());

            int i = mismatches.isEmpty() ? -1 : mismatches.get(0);
            if (i == -1) continue;

            for (int j = i + 1; j < n; j++) {
                if (current.str.charAt(j) == s2.charAt(j) || current.str.charAt(j) != s2.charAt(i)) continue;

                String next = swap(current.str, i, j);
                if (next.equals(s2)) return current.k + 1;

                if (visited.add(next)) {
                    queue.add(new State(next, current.k + 1));
                }
            }
        }

        return -1;
    }

    private String swap(String s, int i, int j) {
        char[] arr = s.toCharArray();
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return new String(arr);
    }

    private static class State {
        String str;
        int k;

        State(String s, int k) {
            this.str = s;
            this.k = k;
        }
    }
}