854. K-Similar Strings

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.

From: LeetCode
Link: 854. K-Similar Strings

Solution:

Ideas:

• Goal: Find the minimum number of swaps to transform s1 into s2.
• Approach: Use BFS (Breadth-First Search) because it guarantees the shortest sequence of swaps.
• Steps:
  • Start with the initial string s1.
  • At each step, find the first mismatch index i where s1[i] != s2[i].
  • Only consider swaps that put the correct s2[i] into position i (reduces branching).
  • Prefer swaps that also fix another mismatch at the same time.
  • Each valid swap generates a new string state.
  • Use a hash set to mark visited states to avoid revisiting.
  • BFS levels correspond to swap counts → the first time we reach s2, the depth is the answer.
• Why it works:
  • BFS explores all possible transformations in increasing swap order.
  • Pruning ensures only useful swaps are explored.

Code:

/*
BFS with pruning:
- At each level, find the first index i where cur[i] != s2[i].
- Only generate neighbors by swapping cur[i] with positions j>i where cur[j] == s2[i].
- Prefer swaps where cur[j] != s2[j] to reduce branching.
This is optimal because every swap fixes at least one mismatch, and BFS finds the minimal swaps.
*/

#define HASH_CAP 100003  // a large prime for hash buckets

// ---------- simple hash set for strings ----------
typedef struct HNode {
    char *key;
    struct HNode *next;
} HNode;

static HNode *htable[HASH_CAP];

static unsigned long djb2(const char *str) {
    unsigned long hash = 5381;
    int c;
    while ((c = (unsigned char)*str++)) hash = ((hash << 5) + hash) + c;
    return hash;
}

static bool h_exist(const char *s) {
    unsigned long h = djb2(s) % HASH_CAP;
    HNode *p = htable[h];
    while (p) {
        if (strcmp(p->key, s) == 0) return true;
        p = p->next;
    }
    return false;
}

static void h_insert(char *s_take_ownership) {
    unsigned long h = djb2(s_take_ownership) % HASH_CAP;
    HNode *node = (HNode *)malloc(sizeof(HNode));
    node->key = s_take_ownership;
    node->next = htable[h];
    htable[h] = node;
}

// ---------- simple queue of char* ----------
typedef struct {
    char **data;
    int head, tail, cap;
} Queue;

static void q_init(Queue *q, int cap) {
    q->data = (char **)malloc(sizeof(char*) * cap);
    q->head = q->tail = 0;
    q->cap = cap;
}

static bool q_empty(Queue *q) {
    return q->head == q->tail;
}

static void q_push(Queue *q, char *s) {
    int nxt = (q->tail + 1) % q->cap;
    if (nxt == q->head) {
        // grow
        int newcap = q->cap * 2;
        char **nd = (char **)malloc(sizeof(char*) * newcap);
        int sz = (q->tail - q->head + q->cap) % q->cap;
        for (int i = 0; i < sz; ++i) {
            nd[i] = q->data[(q->head + i) % q->cap];
        }
        free(q->data);
        q->data = nd;
        q->head = 0;
        q->tail = sz;
        q->cap = newcap;
    }
    q->data[q->tail] = s;
    q->tail = (q->tail + 1) % q->cap;
}

static char* q_pop(Queue *q) {
    char *s = q->data[q->head];
    q->head = (q->head + 1) % q->cap;
    return s;
}

// ---------- main solver ----------
int kSimilarity(char* s1, char* s2) {
    if (strcmp(s1, s2) == 0) return 0;
    int n = (int)strlen(s1);

    // clear hash table (in case of multiple test runs)
    for (int i = 0; i < HASH_CAP; ++i) htable[i] = NULL;

    Queue q; q_init(&q, 1024);

    // enqueue initial
    char *start = strdup(s1);
    q_push(&q, start);
    h_insert(start); // visited owns the same pointer; we won't free strings individually

    int steps = 0;

    while (!q_empty(&q)) {
        int levelSize = (q.tail - q.head + q.cap) % q.cap;
        while (levelSize--) {
            char *cur = q_pop(&q);
            if (strcmp(cur, s2) == 0) return steps;

            // find first mismatch
            int i = 0;
            while (i < n && cur[i] == s2[i]) ++i;
            if (i == n) return steps; // already equal

            // generate neighbors by swapping i with j>i where cur[j] == s2[i]
            // first pass: prefer cur[j] != s2[j] to fix two mismatches at once
            bool madePreferred = false;

            for (int pass = 0; pass < 2; ++pass) {
                for (int j = i + 1; j < n; ++j) {
                    if (cur[j] != s2[i]) continue;
                    if (pass == 0 && cur[j] == s2[j]) continue; // skip in pass 0
                    // create next state
                    char *next = strdup(cur);
                    char tmp = next[i];
                    next[i] = next[j];
                    next[j] = tmp;

                    if (!h_exist(next)) {
                        h_insert(next);
                        q_push(&q, next);
                    } else {
                        free(next);
                    }
                    madePreferred = true;
                }
                if (madePreferred) break; // don't do pass 2 if we added preferred neighbors
            }
            // NOTE: we do not free(cur) because visited keeps the same pointer.
        }
        ++steps;
    }
    return -1; // should not happen for anagrams
}