Find the string from an array that can be converted to a string S with minimum number of swaps

// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check is two // strings are anagrams bool checkIsAnagram(vector<int> charCountS,  vector<int> charCountS1) {  for (int i = 0; i < 26; i++) {  if (charCountS[i] != charCountS1[i])  return false;  }  return true; } // Function to return the frequency of // characters in the array of strings vector<int> getCharCount(string S) {  vector<int> charCount(26, 0);  for (char i : S)  charCount[i - 'a']++;  return charCount; } // Function to return the count of // indices to the left of this index int get(vector<int>& fenwickTree, int index) {  int leftShift = 0;  leftShift += fenwickTree[index];  while (index > 0) {  index -= (-index) & index;  leftShift += fenwickTree[index];  }  return leftShift; } // Update function of Fenwick Tree void update(vector<int>& fenwickTree, int index) {  while (index < fenwickTree.size()) {  fenwickTree[index]++;  index += (-index) & index;  } } // Function to get all positions of // characters present in the string S1 vector<vector<int> > getPositions(string S) {  //@SuppressWarnings("unchecked")  vector<vector<int> > charPositions(26);  for (int i = 0; i < S.size(); i++)  charPositions[i - 'a'].push_back(i);  return charPositions; } // Function to return the minimum number // of swaps required to convert S1 to S int findMinMoves(string S, string S1) {  // cout<<"run\n";  // Stores number of swaps  int minMoves = 0;  // Initialize Fenwick Tree  vector<int> fenwickTree(S.size() + 1);  // Get all positions of characters  // present in the string S1  vector<int> charPositions[26];  int j = 0;  for (char i : S1) {  charPositions[i - 'a'].push_back(j);  j++;  }  // cout<<charPositions[2].size()<<endl;  // Traverse the given string in reverse  for (int i = S.size() - 1; i >= 0; i--) {  // Get the list corresponding  // to character S[i]  vector<int> temp = charPositions[S[i] - 'a'];  // Size of the list  int size = temp.size() - 1;  // Get and remove last  // indices from the list  int index = temp[size] + 1;  charPositions[S[i] - 'a'].pop_back();  // temp.pop_back();  // Count of indices to  // the left of this index  int leftShift = get(fenwickTree, index);  // Update Fenwick T ree  update(fenwickTree, index);  // Shift the index to it's left  index -= leftShift;  // Update moves  minMoves += abs(i - index + 1);  }  // Return moves  return minMoves; } // Function to find anagram of S // requiring minimum number of swaps string getBeststring(string S, vector<string> group) {  // Initialize variables  bool isAnagram = false;  string beststring = "";  int minMoves = INT_MAX;  // Count frequency of characters in S  vector<int> charCountS = getCharCount(S);  // Traverse the array of strings  for (string S1 : group) {  // Count frequency of characters in S1  vector<int> charCountS1 = getCharCount(S1);  // cout<<S1<<endl;  // Check if S1 is anagram of S  bool anagram  = checkIsAnagram(charCountS, charCountS1);  // cout<<anagram<<endl;  // If not an anagram of S  if (anagram == 0)  continue;  isAnagram = true;  // Count swaps required  // to convert S to S1  int moves = findMinMoves(S, S1);  // cout<<moves<<endl;  // Count minimum number of swaps  if (moves < minMoves) {  minMoves = moves;  beststring = S1;  }  }  // If no anagram is found, print -1  return (isAnagram) ? beststring : "-1"; } // Driver Code int main() {  // Given string  string S = "abcdac";  // Given array of strings  vector<string> arr = { "cbdaca", "abcacd", "abcdef" };  string beststring = getBeststring(S, arr);  // Print answer  cout << (beststring) << endl; } // This code is contributed by mohit kumar 29