Solution.java

class Solution {
    
    int min;
    public int kSimilarity(String A, String B) {
        if(A.length() != B.length()) return Integer.MAX_VALUE;
        
        min = Integer.MAX_VALUE;
        char [] a = A.toCharArray();
        helper(a, B, 0, 0);
        return min;
    }
    
    void helper(char [] a, String b, int i, int swaps){
        if(i == a.length){
            min = Math.min(min, swaps);
            return;
        }
        if(a[i] == b.charAt(i))
            helper(a, b, i+1, swaps);
        else{
            if(swaps+1 > min) return;
            for(int j = i+1; j < a.length; ++j){
                if(a[j] != b.charAt(i)) continue;
                swap(a, i, j);
                helper(a, b, i+1, swaps+1);
                swap(a, i, j);
            }
        }
    }
    
    void swap(char [] a, int i, int j){
        char temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}