Convert string X to an anagram of string Y with minimum replacements - Coding

Given two strings X and Y, we need to convert string X into an anagram of string Y with minimum replacements. If we have multiple ways of achieving the target, we go for the lexicographically smaller string where the length of each string $\in [1, 100000]$

Examples:

Input : X = "CDBABC" 
        Y = "ADCABD"
Output : Anagram : ADBADC
         Number of changes made: 2

Input : X = "PJPOJOVMAK"
        Y = "FVACRHLDAP"
Output : Anagram : ACPDFHVLAR
         Number of changes made: 7

Approach used: We have to convert string X into a lexicographically smallest anagram of string Y doing minimum replacements in the original string X. We maintain two counter arrays that store the count/frequency of each character in the two strings. Let counters of the two strings be $Count_{x}$ and $Count_{y}$ . Now, anagrams by definition mean that the frequency of the characters in two anagrams is always equal. Thus, to convert string X into an anagram of string Y, the frequency of characters should be equal. Therefore, the total number of alteration we need to make in total to convert string X into an anagram of string Y is $(\sum |Count_{x_{i}} - Count_{y_{i}}|)/2$ , where we iterate for each character i.

Half the job is done as we know how many replacements are to be done. We now need the lexicographically smaller string. Now, for a specific position, we look for all possible characters from ‘A’ to ‘Z’ and check for each character whether it could be fit in this position or now. For a better understanding, we iterate for each position in the string. Check if is there is a character that is there in string Y and not in string X (or the frequency of character is more in string Y and less in string X). Now, if there is one, we check that the character at the current position in X, is it unnecessary? i.e. does it have more frequency in string X and less frequency in string Y. Now, if all the boxes are ticked, we further check if we insert the character in this position, as we need to generate the lexicographically smaller string. If all the conditions are true, we replace the character in string X with the character in string Y. After all such replacements, we can print the altered string X as the output.

Implementation:

C++

// C++ program to convert string X to
// string Y which minimum number of changes.
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 26
 
// Function that converts string X
// into lexicographically smallest
// anagram of string Y with minimal changes
void printAnagramAndChanges(string X, string Y)
{
    int countx[MAX] = {0}, county[MAX] = {0},
        ctrx[MAX] = {0}, ctry[MAX] = {0};
 
    int change = 0;
    int l = X.length();
 
    // Counting frequency of characters
    // in each string.
    for (int i = 0; i < l; i++) {
        countx[X[i] - 'A']++;
        county[Y[i] - 'A']++;
    }
 
    // We maintain two more counter arrays 
    // ctrx[] and ctry[]
    // Ctrx[] maintains the count of extra 
    // elements present in string X than 
    // string Y
    // Ctry[] maintains the count of
    // characters missing from string X
    // which should be present in string Y.
    for (int i = 0; i < MAX; i++) {
        if (countx[i] > county[i])
            ctrx[i] += (countx[i] - county[i]);
        else if (countx[i] < county[i])
            ctry[i] += (county[i] - countx[i]);
        change += abs(county[i] - countx[i]);
    }
 
    for (int i = 0; i < l; i++) {
 
        // This means that we cannot edit the
        // current character as it's frequency
        // in string X is equal to or less
        // than the frequency in string Y.
        // Thus, we go to the next position
        if (ctrx[X[i] - 'A'] == 0)
            continue;
 
        // Here, we try to find that character,
        // which has more frequency in string Y
        // and less in string X. We try to find
        // this character in lexicographical
        // order so that we get
        // lexicographically smaller string
        int j;
        for (j = 0; j < MAX; j++)
            if ((ctry[j]) > 0)
                break;
 
        // This portion deals with the
        // lexicographical property.
        // Now, we put a character in string X
        // when either this character has smaller
        // value than the character present there
        // right now or if this is the last position
        // for it to exchange, else we fix the
        // character already present here in
        // this position.
        if (countx[X[i] - 'A'] == ctrx[X[i] - 'A']
            || X[i] - 'A' > j) {
 
            countx[X[i] - 'A']--;
            ctrx[X[i] - 'A']--;
            ctry[j]--;
            X[i] = 'A' + j;
        }
        else
            countx[X[i] - 'A']--;
    }
 
    cout << "Anagram : " << X << endl;
    cout << "Number of changes made : " << change / 2;
}
 
// Driver program
int main()
{
    string x = "CDBABC", y = "ADCABD";
    printAnagramAndChanges(x, y);
    return 0;
}

Java

// Java program to convert string X to 
// string Y which minimum number of changes. 
class GFG 
{
 
    static final int MAX = 26;
 
    // Function that converts string X 
    // into lexicographically smallest 
    // anagram of string Y with minimal changes 
    static void printAnagramAndChanges(char[] X,
                                        char[] Y)
    {
        int countx[] = new int[MAX], county[] = new int[MAX],
            ctrx[] = new int[MAX], ctry[] = new int[MAX];
 
        int change = 0;
        int l = X.length;
 
        // Counting frequency of characters 
        // in each string. 
        for (int i = 0; i < l; i++)
        {
            countx[X[i] - 'A']++;
            county[Y[i] - 'A']++;
        }
 
        // We maintain two more counter arrays 
        // ctrx[] and ctry[] 
        // Ctrx[] maintains the count of extra 
        // elements present in string X than 
        // string Y 
        // Ctry[] maintains the count of 
        // characters missing from string X 
        // which should be present in string Y. 
        for (int i = 0; i < MAX; i++) 
        {
            if (countx[i] > county[i]) 
            {
                ctrx[i] += (countx[i] - county[i]);
            }
            else if (countx[i] < county[i])
            {
                ctry[i] += (county[i] - countx[i]);
            }
            change += Math.abs(county[i] - countx[i]);
        }
 
        for (int i = 0; i < l; i++) 
        {
 
            // This means that we cannot edit the 
            // current character as it's frequency 
            // in string X is equal to or less 
            // than the frequency in string Y. 
            // Thus, we go to the next position 
            if (ctrx[X[i] - 'A'] == 0)
            {
                continue;
            }
 
            // Here, we try to find that character, 
            // which has more frequency in string Y 
            // and less in string X. We try to find 
            // this character in lexicographical 
            // order so that we get 
            // lexicographically smaller string 
            int j;
            for (j = 0; j < MAX; j++)
            {
                if ((ctry[j]) > 0)
                {
                    break;
                }
            }
 
            // This portion deals with the 
            // lexicographical property. 
            // Now, we put a character in string X 
            // when either this character has smaller 
            // value than the character present there 
            // right now or if this is the last position 
            // for it to exchange, else we fix the 
            // character already present here in 
            // this position. 
            if (countx[X[i] - 'A'] == ctrx[X[i] - 'A']
                || X[i] - 'A' > j) 
            {
 
                countx[X[i] - 'A']--;
                ctrx[X[i] - 'A']--;
                ctry[j]--;
                X[i] = (char) ('A' + j);
            } 
            else
            {
                countx[X[i] - 'A']--;
            }
        }
        System.out.println("Anagram : " + String.valueOf(X));
        System.out.println("Number of changes made : " + change / 2);
    }
 
    // Driver code 
    public static void main(String[] args) 
    {
        String x = "CDBABC", y = "ADCABD";
        printAnagramAndChanges(x.toCharArray(), y.toCharArray());
    }
} 
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program to convert string X to
# string Y which minimum number of changes.
MAX = 26
 
# Function that converts string X
# into lexicographically smallest
# anagram of string Y with minimal changes
def printAnagramAndChanges(x, y):
    x = list(x)
    y = list(y)
    countx, county = [0] * MAX, [0] * MAX
    ctrx, ctry = [0] * MAX, [0] * MAX
 
    change = 0
    l = len(x)
 
    # Counting frequency of characters
    # in each string.
    for i in range(l):
        countx[ord(x[i]) - ord('A')] += 1
        county[ord(y[i]) - ord('A')] += 1
 
    # We maintain two more counter arrays
    # ctrx[] and ctry[]
    # Ctrx[] maintains the count of extra
    # elements present in string X than
    # string Y
    # Ctry[] maintains the count of
    # characters missing from string X
    # which should be present in string Y.
    for i in range(MAX):
        if countx[i] > county[i]:
            ctrx[i] += (countx[i] - county[i])
        elif countx[i] < county[i]:
            ctry[i] += (county[i] - countx[i])
        change += abs(county[i] - countx[i])
 
    for i in range(l):
 
        # This means that we cannot edit the
        # current character as it's frequency
        # in string X is equal to or less
        # than the frequency in string Y.
        # Thus, we go to the next position
        if ctrx[ord(x[i]) - ord('A')] == 0:
            continue
 
        # Here, we try to find that character,
        # which has more frequency in string Y
        # and less in string X. We try to find
        # this character in lexicographical
        # order so that we get
        # lexicographically smaller string
        j = 0
        for j in range(MAX):
            if ctry[j] > 0:
                break
 
        # This portion deals with the
        # lexicographical property.
        # Now, we put a character in string X
        # when either this character has smaller
        # value than the character present there
        # right now or if this is the last position
        # for it to exchange, else we fix the
        # character already present here in
        # this position.
        if countx[ord(x[i]) -
                ord('A')] == ctrx[ord(x[i]) - ord('A')] or \
                                  ord(x[i]) - ord('A') > j:
            countx[ord(x[i]) - ord('A')] -= 1
            ctrx[ord(x[i]) - ord('A')] -= 1
            ctry[j] -= 1
            x[i] = chr(ord('A') + j)
        else:
            countx[ord(x[i]) - ord('A')] -= 1
 
    print("Anagram :", ''.join(x))
    print("Number of changes made :", change // 2)
 
# Driver Code
if __name__ == "__main__":
    x = "CDBABC"
    y = "ADCABD"
    printAnagramAndChanges(x, y)
 
# This code is contributed by
# sanjeev2552

C#

// C# program to convert string X to 
// string Y which minimum number of changes.
using System;
 
class GFG 
{ 
 
    static readonly int MAX = 26; 
 
    // Function that converts string X 
    // into lexicographically smallest 
    // anagram of string Y with minimal changes 
    static void printAnagramAndChanges(char[] X, 
                                        char[] Y) 
    { 
        int []countx = new int[MAX]; 
        int []county = new int[MAX];
        int []ctrx = new int[MAX];
        int []ctry = new int[MAX]; 
 
        int change = 0; 
        int l = X.Length; 
 
        // Counting frequency of characters 
        // in each string. 
        for (int i = 0; i < l; i++) 
        { 
            countx[X[i] - 'A']++; 
            county[Y[i] - 'A']++; 
        } 
 
        // We maintain two more counter arrays 
        // ctrx[] and ctry[] 
        // Ctrx[] maintains the count of extra 
        // elements present in string X than 
        // string Y 
        // Ctry[] maintains the count of 
        // characters missing from string X 
        // which should be present in string Y. 
        for (int i = 0; i < MAX; i++) 
        { 
            if (countx[i] > county[i]) 
            { 
                ctrx[i] += (countx[i] - county[i]); 
            } 
            else if (countx[i] < county[i]) 
            { 
                ctry[i] += (county[i] - countx[i]); 
            } 
            change += Math.Abs(county[i] - countx[i]); 
        } 
 
        for (int i = 0; i < l; i++) 
        { 
 
            // This means that we cannot edit the 
            // current character as it's frequency 
            // in string X is equal to or less 
            // than the frequency in string Y. 
            // Thus, we go to the next position 
            if (ctrx[X[i] - 'A'] == 0) 
            { 
                continue; 
            } 
 
            // Here, we try to find that character, 
            // which has more frequency in string Y 
            // and less in string X. We try to find 
            // this character in lexicographical 
            // order so that we get 
            // lexicographically smaller string 
            int j; 
            for (j = 0; j < MAX; j++) 
            { 
                if ((ctry[j]) > 0) 
                { 
                    break; 
                } 
            } 
 
            // This portion deals with the 
            // lexicographical property. 
            // Now, we put a character in string X 
            // when either this character has smaller 
            // value than the character present there 
            // right now or if this is the last position 
            // for it to exchange, else we fix the 
            // character already present here in 
            // this position. 
            if (countx[X[i] - 'A'] == ctrx[X[i] - 'A'] 
                || X[i] - 'A' > j) 
            { 
 
                countx[X[i] - 'A']--; 
                ctrx[X[i] - 'A']--; 
                ctry[j]--; 
                X[i] = (char) ('A' + j); 
            } 
            else
            { 
                countx[X[i] - 'A']--; 
            } 
        } 
        Console.WriteLine("Anagram : " +
                        String.Join("",X)); 
        Console.WriteLine("Number of changes made : " +
                            change / 2); 
    } 
 
    // Driver code 
    public static void Main(String[] args) 
    { 
        String x = "CDBABC", y = "ADCABD"; 
        printAnagramAndChanges(x.ToCharArray(),
                                y.ToCharArray()); 
    } 
} 
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
      // JavaScript program to convert string X to
      // string Y which minimum number of changes.
      const MAX = 26;
 
      // Function that converts string X
      // into lexicographically smallest
      // anagram of string Y with minimal changes
      function printAnagramAndChanges(X, Y) 
      {
        var countx = new Array(MAX).fill(0);
        var county = new Array(MAX).fill(0);
        var ctrx = new Array(MAX).fill(0);
        var ctry = new Array(MAX).fill(0);
 
        var change = 0;
        var l = X.length;
 
        // Counting frequency of characters
        // in each string.
        for (var i = 0; i < l; i++) {
          countx[X[i].charCodeAt(0) - "A".charCodeAt(0)]++;
          county[Y[i].charCodeAt(0) - "A".charCodeAt(0)]++;
        }
 
        // We maintain two more counter arrays
        // ctrx[] and ctry[]
        // Ctrx[] maintains the count of extra
        // elements present in string X than
        // string Y
        // Ctry[] maintains the count of
        // characters missing from string X
        // which should be present in string Y.
        for (var i = 0; i < MAX; i++) {
          if (countx[i] > county[i]) {
            ctrx[i] += countx[i] - county[i];
          } else if (countx[i] < county[i]) {
            ctry[i] += county[i] - countx[i];
          }
          change += Math.abs(county[i] - countx[i]);
        }
 
        for (var i = 0; i < l; i++) {
          // This means that we cannot edit the
          // current character as it's frequency
          // in string X is equal to or less
          // than the frequency in string Y.
          // Thus, we go to the next position
          if (ctrx[X[i].charCodeAt(0) - 
          "A".charCodeAt(0)] === 0) 
          {
            continue;
          }
 
          // Here, we try to find that character,
          // which has more frequency in string Y
          // and less in string X. We try to find
          // this character in lexicographical
          // order so that we get
          // lexicographically smaller string
          var j;
          for (j = 0; j < MAX; j++) {
            if (ctry[j] > 0) {
              break;
            }
          }
 
          // This portion deals with the
          // lexicographical property.
          // Now, we put a character in string X
          // when either this character has smaller
          // value than the character present there
          // right now or if this is the last position
          // for it to exchange, else we fix the
          // character already present here in
          // this position.
          if (
            countx[X[i].charCodeAt(0) - "A".charCodeAt(0)] ===
              ctrx[X[i].charCodeAt(0) - "A".charCodeAt(0)] ||
            X[i].charCodeAt(0) - "A".charCodeAt(0) > j
          ) {
            countx[X[i].charCodeAt(0) - "A".charCodeAt(0)]--;
            ctrx[X[i].charCodeAt(0) - "A".charCodeAt(0)]--;
            ctry[j]--;
            X[i] = String.fromCharCode("A".charCodeAt(0) + j);
          } else {
            countx[X[i].charCodeAt(0) - "A".charCodeAt(0)]--;
          }
        }
        document.write("Anagram : " + X.join("") + "<br>");
        document.write("Number of changes made : " + change / 2);
      }
 
      // Driver code
      var x = "CDBABC",
          y = "ADCABD";
      printAnagramAndChanges(x.split(""), y.split(""));
       
</script>

Output

Anagram : ADBADC
Number of changes made : 2

Time Complexity: O(N), as we are using a loop to traverse N times. Where N is the length of the string.
Auxiliary Space: O(4*26), as we are using extra space.

Reffered: https://www.geeksforgeeks.org

Strings

Related
K distant string
Strings
Strings
Reduce Hamming distance by swapping two characters
Reduce Hamming distance by swapping two characters

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	15