Program to find value of K for K-Similar Strings in C++

Suppose we have two strings s and t. These two strings are K-similar when we can swap the positions of two letters in s exactly K times so that the resulting string is t. We have two anagrams s and t, and we have to find the smallest K for which s and t are K-similar.

So, if the input is like s = "abc", t = "bac", then the output will be 1.

To solve this, we will follow these steps −

• Define a function swapp(), this will take string s, i, j,

• x := s[i], y := s[j]

• s[i] := y, s[j] := x

• From the main method do the following −

• if A is same as B, then:, return 0

• Define one set visited

• insert A into visited

• Define one queue q, insert A into q

• for initialize lvl := 1, when not q is empty, update (increase lvl by 1), do −

  • sz := size of q

  • while sz is non-zero, decrease sz by 1 in each iteration, do:

    • curr := first element of q

    • delete element from q

    • i := 0

    • while (i < size of curr and curr[i] is same as B[i]), do

      • (increase i by 1)

    • for initialize j := i + 1, when j < size of curr, update (increase j by 1), do

      • if curr[i] is same as curr[j], then:

        • Ignore following part, skip to the next iteration

      • if curr[j] is not equal to B[i], then:

        • Ignore following part, skip to the next iteration

      • if curr[j] is same as B[j], then:

        • Ignore following part, skip to the next iteration

      • swapp(curr, i, j)

      • if curr is same as B, then:

        • return lvl

      • if not call count(curr) of visited, then:

        • insert curr into visited

        • insert curr into q

      • swapp(curr, i, j)

• return -1

Example

Let us see the following implementation to get better understanding

#include <bits/stdc++.h> using namespace std; class Solution { public:    int kSimilarity(string A, string B) {       if (A == B)          return 0;       unordered_set<string> visited;       visited.insert(A);       queue<string> q;       q.push(A);       for (int lvl = 1; !q.empty(); lvl++) {          int sz = q.size();          while (sz--) {             string curr = q.front();             q.pop();             int i = 0;             while (i < curr.size() && curr[i] == B[i])                i++;             for (int j = i + 1; j < curr.size(); j++) {                if (curr[i] == curr[j])                   continue;                if (curr[j] != B[i])                   continue;                if (curr[j] == B[j])                   continue;                swapp(curr, i, j);                if (curr == B)                   return lvl;                if (!visited.count(curr)) {                   visited.insert(curr);                   q.push(curr);                }                swapp(curr, i, j);             }          }       }       return -1;    }    void swapp(string &s, int i, int j) {       char x = s[i];       char y = s[j];       s[i] = y;       s[j] = x;    } }; main(){ Solution ob; cout << (ob.kSimilarity("abc", "bac")); }

Input

"abc", "bac"

Output

1