Given a string S and an array of strings arr[] of length N and M respectively, the task is to find the string from the given array to the string S by swapping minimum number of characters . If no string can be converted to S, print -1.
Examples:
Input: S = “abc”, arr[] = {“acb”, “xyz”}
Output: acb
Explanation:
The string “acb” can be converted to “abc” by swapping 1 pair of characters “acb” -> “abc“.
The string”xyz” cannot be converted to “abc”.
Input: S = “abc”, arr[] = {“ab”, “xy”, “cb”}
Output: -1
Approach: The problem can be solved by searching for anagrams of S from the given array of strings and then, for every such string, find the minimum number of character swaps required to convert the string to S.
Follow the steps below to solve the problem:
- Traverse the array of strings and for each string present in the array, check if it is an anagram of S or not.
- If no such string is found, then print -1.
- Otherwise, find the minimum number of swaps required to convert the current string into S, by iterating over the characters of the current string, say S1.
- Store the position of characters in S1 in 26 lists. For each character in S1, append its index to its corresponding list, i.e., list 0 stores all positions of the character ‘a’. Similarly, list 1 stores all positions of ‘b’ and so on.
- After complete traversal of the string S1, iterate over the characters of the string S in reverse and for each character, say S[j], get its respective index from the given array of lists, say temp.
- Now, the optimal move is to move the character at the last index in temp to the index j. This is optimal because:
- Characters are being moved in every move. Hence, no move is being wasted.
- The last index in temp would be closer to j than other indices as the string is being iterated in reverse.
- To optimize, a Fenwick tree can be used to determine the modified positions of characters in S1, in case of any swaps.
Illustration:
Suppose, S = “abca”, S1 = “cbaa”
Below is the list generated for S1:
List for ‘a’ = {2, 3}
List for ‘b’ = {1}
List for ‘c’ = {0}
Iterate over the characters of S, in reverse, by initializing minMoves with 0.
- S = “abca”, i = 3
Remove last index from list corresponding to ‘a’, i.e. 3.
Search the Fenwick Tree to check if there are any indices to the left of this index in the Fenwick Tree or not.
Since the tree is empty now, no need to shift this index.
Add index 3 to the Fenwick Tree.
minMoves += (i – index) = (3 – 3). Therefore, minMoves = 0- S = “abca”, i = 2
Remove the last index from list corresponding to ‘c’, i.e. 0.
Search the Fenwick Tree to check if there are any indices to the left of this index in the Fenwick Tree or not.
Since the only index in the tree is 3, and it is to the right of 0, no need to shift this index.
Add index 0 to the Fenwick Tree.
minMoves += (i – index) = (2 – 0). Therefore, minMoves = 2- S = “abca”, i = 1
Remove last index from list corresponding to ‘b’, i.e. 1.
Search the Fenwick Tree to check if there are any indices to the left of this index in the Fenwick Tree or not.
The count obtained is 1, i.e. there was one character to the left of index 1, which is now, towards it’s right.
Add index 1 to the Fenwick Tree.
new index = 1 – leftShit = 1 – 1 = 0
minMoves += (i – new index) = 1 – 0 = 3- S = “abca”, i= 0
Remove last index from list corresponding to ‘a’, i.e. 2.
Search the Fenwick Tree to check if there are any indices to the left of this index in the Fenwick tree or not.
The count obtained is 2, i.e. there were two characters to the left of index 2, which is now, towards its right.
Add index 2 to the Fenwick Tree.
new index = 2 – leftShit = 2 – 2 = 0
minMoves+= (i-new index) = 0 – 0 = 3
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check is two// strings are anagramsbool 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 stringsvector<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 indexint 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 Treevoid 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 S1vector<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 Sint 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 swapsstring 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 Codeint 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 |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find anagram of S // requiring minimum number of swaps static String getBestString(String S, List<String> group) { // Initialize variables boolean isAnagram = false; String bestString = null; int minMoves = Integer.MAX_VALUE; // Count frequency of characters in S int[] charCountS = getCharCount(S); // Traverse the array of strings for (String S1 : group) { // Count frequency of characters in S1 int[] charCountS1 = getCharCount(S1); // Check if S1 is anagram of S boolean anagram = checkIsAnagram(charCountS, charCountS1); // If not an anagram of S if (!anagram) continue; isAnagram = true; // Count swaps required // to convert S to S1 int moves = findMinMoves(S, S1); // Count minimum number of swaps if (moves < minMoves) { minMoves = moves; bestString = S1; } } // If no anagram is found, print -1 return (isAnagram) ? bestString : "-1"; } // Function to return the minimum number // of swaps required to convert S1 to S static int findMinMoves(String S, String S1) { // Stores number of swaps int minMoves = 0; // Initialize Fenwick Tree int[] fenwickTree = new int[S.length() + 1]; // Get all positions of characters // present in the string S1 List<List<Integer> > charPositions = getPositions(S1); // Traverse the given string in reverse for (int i = S.length() - 1; i >= 0; i--) { // Get the list corresponding // to character S[i] List<Integer> temp = charPositions.get(S.charAt(i) - 'a'); // Size of the list int size = temp.size() - 1; // Get and remove last // indices from the list int index = temp.remove(size) + 1; // 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 += Math.abs(i - index + 1); } // Return moves return minMoves; } // Function to get all positions of // characters present in the string S1 static List<List<Integer> > getPositions(String S) { @SuppressWarnings("unchecked") List<List<Integer> > charPositions = new ArrayList(); for (int i = 0; i < 26; i++) charPositions.add(new ArrayList<Integer>()); for (int i = 0; i < S.length(); i++) charPositions.get(S.charAt(i) - 'a').add(i); return charPositions; } // Update function of Fenwick Tree static void update(int[] fenwickTree, int index) { while (index < fenwickTree.length) { fenwickTree[index]++; index += (-index) & index; } } // Function to return the count of // indices to the left of this index static int get(int[] fenwickTree, int index) { int leftShift = 0; leftShift += fenwickTree[index]; while (index > 0) { index -= (-index) & index; leftShift += fenwickTree[index]; } return leftShift; } // Function to return the frequency of // characters in the array of strings static int[] getCharCount(String S) { int[] charCount = new int[26]; for (int i = 0; i < S.length(); i++) charCount[S.charAt(i) - 'a']++; return charCount; } // Function to check is two // strings are anagrams static boolean checkIsAnagram(int[] charCountS, int[] charCountS1) { for (int i = 0; i < 26; i++) { if (charCountS[i] != charCountS1[i]) return false; } return true; } // Driver Code public static void main(String[] args) { // Given string String S = "abcdac"; // Given array of strings String arr[] = { "cbdaca", "abcacd", "abcdef" }; String bestString = getBestString(S, Arrays.asList(arr)); // Print answer System.out.println(bestString); }} |
Python3
# Python program for the above approachimport math# Function to check is two# strings are anagramsdef checkIsAnagram(charCountS, charCountS1): for i in range(26): if charCountS[i] != charCountS1[i]: return False return True# Function to return the frequency of# characters in the array of stringsdef getCharCount(S): charCount = [0] * 26 for i in S: charCount[ord(i) - ord('a')] += 1 return charCount# Function to return the count of# indices to the left of this indexdef get(fenwickTree, index): leftShift = 0 leftShift += fenwickTree[index] while index > 0: index -= (-index) & index leftShift += fenwickTree[index] return leftShift# Update function of Fenwick Treedef update(fenwickTree, index): while index < len(fenwickTree): fenwickTree[index] += 1 index += (-index) & index# Function to get all positions of# characters present in the string S1def getPositions(S): charPositions = [[] for _ in range(26)] for i in range(len(S)): charPositions[ord(S[i]) - ord('a')].append(i) return charPositions# Function to return the minimum number# of swaps required to convert S1 to Sdef findMinMoves(S, S1): # Stores number of swaps minMoves = 0 # Initialize Fenwick Tree fenwickTree = [0] * (len(S) + 1) charPositions = [[] for _ in range(26)] j = 0 for i in S1: charPositions[ord(i) - ord('a')].append(j) j += 1 for i in range(len(S) - 1, -1, -1): temp = charPositions[ord(S[i]) - ord('a')] size = len(temp) - 1 index = temp[size] + 1 charPositions[ord(S[i]) - ord('a')].pop() leftShift = get(fenwickTree, index) update(fenwickTree, index) index -= leftShift minMoves += abs(i - index + 1) return minMoves# Function to find anagram of S# requiring minimum number of swapsdef getBeststring(S, group): isAnagram = False beststring = "" minMoves = math.inf # Count frequency of characters in S charCountS = getCharCount(S) for S1 in group: # Count frequency of characters in S1 charCountS1 = getCharCount(S1) # Check if S1 is anagram of S anagram = checkIsAnagram(charCountS, charCountS1) if not anagram: continue isAnagram = True # Count swaps required # to convert S to S1 moves = findMinMoves(S, S1) # Count minimum number of swaps if moves < minMoves: minMoves = moves beststring = S1 # If no anagram is found, print -1 return beststring if isAnagram else "-1"# Driver Code# Give StringS = "abcdac"# Given array of stringsarr = ["cbdaca", "abcacd", "abcdef"]beststring = getBeststring(S, arr)print(beststring)# This code is contributed by adityashae15 |
Javascript
// Javascript equivalent// Function to check is two// strings are anagramsfunction checkIsAnagram(charCountS, charCountS1) { for (let 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 stringsfunction getCharCount(S) { let charCount = new Array(26).fill(0); for (let i = 0; i < S.length; i++) { charCount[S.charCodeAt(i) - 'a'.charCodeAt()]++; } return charCount;}// Function to return the count of// indices to the left of this indexfunction get(fenwickTree, index) { let leftShift = 0; leftShift += fenwickTree[index]; while (index > 0) { index -= (-index) & index; leftShift += fenwickTree[index]; } return leftShift;}// Update function of Fenwick Treefunction update(fenwickTree, index) { while (index < fenwickTree.length) { fenwickTree[index]++; index += (-index) & index; }}// Function to get all positions of// characters present in the string S1function getPositions(S) { let charPositions = []; for (let i = 0; i < 26; i++) { charPositions.push([]); } for (let i = 0; i < S.length; i++) { charPositions[S.charCodeAt(i) - 'a'.charCodeAt()].push(i); } return charPositions;}// Function to return the minimum number// of swaps required to convert S1 to Sfunction findMinMoves(S, S1) { // Stores number of swaps let minMoves = 0; // Initialize Fenwick Tree let fenwickTree = new Array(S.length + 1).fill(0); let charPositions = []; for (let i = 0; i < 26; i++) { charPositions.push([]); } let j = 0; for (let i = 0; i < S1.length; i++) { charPositions[S1.charCodeAt(i) - 'a'.charCodeAt()].push(j); j++; } for (let i = S.length - 1; i >= 0; i--) { let temp = charPositions[S.charCodeAt(i) - 'a'.charCodeAt()]; let size = temp.length - 1; let index = temp[size] + 1; charPositions[S.charCodeAt(i) - 'a'.charCodeAt()].pop(); let leftShift = get(fenwickTree, index); update(fenwickTree, index); index -= leftShift; minMoves += Math.abs(i - index + 1); } return minMoves;}// Function to find anagram of S// requiring minimum number of swapsfunction getBeststring(S, group) { let isAnagram = false; let beststring = ""; let minMoves = Number.MAX_VALUE; // Count frequency of characters in S let charCountS = getCharCount(S); for (let S1 of group) { // Count frequency of characters in S1 let charCountS1 = getCharCount(S1); // Check if S1 is anagram of S let anagram = checkIsAnagram(charCountS, charCountS1); if (!anagram) { continue; } isAnagram = true; // Count swaps required // to convert S to S1 let moves = findMinMoves(S, S1); // 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// Give Stringlet S = "abcdac";// Given array of stringslet arr = ["cbdaca", "abcacd", "abcdef"];let beststring = getBeststring(S, arr);console.log(beststring); |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class AnagramSwaps { // Function to check if two // strings are anagrams public static bool CheckIsAnagram(int[] charCountS, 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 public static int[] GetCharCount(string S) { int[] charCount = new int[26]; foreach(char c in S) { charCount++; } return charCount; } // Function to return the count of // indices to the left of this index public static int Get(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 public static void Update(int[] fenwickTree, int index) { while (index < fenwickTree.Length) { fenwickTree[index] += 1; index += (-index) & index; } } // Function to get all positions of // characters present in the string S1 public static List<int>[] GetPositions(string S) { List<int>[] charPositions = new List<int>[ 26 ]; for (int i = 0; i < 26; i++) { charPositions[i] = new List<int>(); } for (int i = 0; i < S.Length; i++) { charPositions[S[i] - 'a'].Add(i); } return charPositions; } // Function to return the minimum number // of swaps required to convert S1 to S public static int FindMinMoves(string S, string S1) { // Stores number of swaps int minMoves = 0; // Initialize Fenwick Tree int[] fenwickTree = new int[S.Length + 1]; List<int>[] charPositions = new List<int>[ 26 ]; for (int i = 0; i < 26; i++) { charPositions[i] = new List<int>(); } int j = 0; foreach(char c in S1) { charPositions.Add(j); j++; } for (int i = S.Length - 1; i >= 0; i--) { List<int> temp = charPositions[S[i] - 'a']; int size = temp.Count - 1; int index = temp[size] + 1; charPositions[S[i] - 'a'].RemoveAt(size); int leftShift = Get(fenwickTree, index); Update(fenwickTree, index); index -= leftShift; minMoves += Math.Abs(i - index + 1); } return minMoves; } // Function to find anagram of S // requiring minimum number of swaps public static string GetBestString(string S, string[] group) { bool isAnagram = false; string bestString = ""; int minMoves = int.MaxValue; // Count frequency of characters in S int[] charCountS = GetCharCount(S); foreach(string S1 in group) { // Count frequency of characters in S1 int[] charCountS1 = GetCharCount(S1); // Check if S1 is anagram of S bool anagram = CheckIsAnagram(charCountS, charCountS1); if (!anagram) continue; isAnagram = true; // Count swaps required to convert S to S1 int moves = FindMinMoves(S, S1); // Count minimum number of swaps if (moves < minMoves) { minMoves = moves; bestString = S1; } } // If no anagram is found, return -1 return isAnagram ? bestString : "-1"; } // Driver Code static void Main(string[] args) { // Give String string S = "abcdac"; // Given array of strings string[] arr = { "cbdaca", "abcacd", "abcdef" }; string bestString = GetBestString(S, arr); Console.WriteLine(bestString); }} |
Output:
abcacd
Time Complexity: O(M * N * logN)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
