Given two equal-size strings s[] and t[] of size N. In one step, choose any character of t[] and replace it with another character. Return the minimum number of steps to make t[] an anagram of s[].
Note: An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.
Examples:
Input: s = “baa”, t = “aba”
Output: 0
Explanation: Both String contains identical charactersInput: s = “ddcf”, t = “cedk”
Output: 2
Explanation: Here, we need to change two characters in either of the strings to make them identical. We can change ‘d’ and ‘f’ in s1 or ‘e’ and ‘k’ in s2.
Hashing Approach: The hashing approach has been discussed in Set 1 of this article. In this article, we will be looking at how to solve this problem using the map.
Approach: The idea is to use Hashing to store the frequencies of every character of the string s[] and then while traversing string t[], check if that character is present in the map or not. If yes, then decrease its value by 1. Else, increase the count by 1. Follow the steps below to solve the problem:
- Initialize the variable count as 0 to store the answer.
- Initialize an unordered_map<char, int> a[] to store the frequencies.
- Iterate over the range [0, N) using the variable i and perform the following steps:
- Increase the value of a[i] by 1.
- Traverse over the string using the variable j and perform the following tasks:
- If a[j] is greater than 0 then decrease the value of a[j] by 1.
- Else, increase the value of count by 1.
- After performing the above steps, print the value of count as the answer.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the minimum changes// to make the 2 strings anagramint minSteps(string s, string t){ unordered_map<char, int> a; // For counting the steps to be changed int count = 0; for (auto i : s) { // Increasing the count if the no. // is present a[i]++; } for (auto j : t) { // Checking if the element of s is // present in t or not if (a[j] > 0) { // If present then decrease the // no. in map by 1 a[j]--; } else { // If not present // increase count by 1 count++; } } cout << count; // Return count return count;}// Driver Codeint main(){ string s = "ddcf", t = "cedk"; minSteps(s, t); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to count the minimum changes // to make the 2 Strings anagram static int minSteps(String s, String t) { HashMap<Character, Integer> a = new HashMap<Character, Integer>(); // For counting the steps to be changed int count = 0; for (char i : s.toCharArray()) { // Increasing the count if the no. // is present if (a.containsKey(i)) { a.put(i, a.get(i) + 1); } else { a.put(i, 1); } } for (char j : t.toCharArray()) { // Checking if the element of s is // present in t or not if (a.containsKey(j)) { // If present then decrease the // no. in map by 1 a.put(j, a.get(j) - 1); } else { // If not present // increase count by 1 count++; } } System.out.print(count); // Return count return count; } // Driver Code public static void main(String[] args) { String s = "ddcf", t = "cedk"; minSteps(s, t); }}// This code is contributed by shikhasingrajput |
Python3
# python program for the above approach# Function to count the minimum changes# to make the 2 strings anagramdef minSteps(s, t): a = {} # For counting the steps to be changed count = 0 for i in s: # Increasing the count if the no. # is present if i in a: a[i] += 1 else: a[i] = 1 for j in t: # Checking if the element of s is # present in t or not if j in a: # If present then decrease the # no. in map by 1 a[j] -= 1 else: # If not present # increase count by 1 count += 1 print(count) # Return count return count# Driver Codeif __name__ == "__main__": s = "ddcf" t = "cedk" minSteps(s, t) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG { // Function to count the minimum changes // to make the 2 Strings anagram static int minSteps(String s, String t) { Dictionary<char, int> a = new Dictionary<char, int>(); // For counting the steps to be changed int count = 0; foreach (char i in s.ToCharArray()) { // Increasing the count if the no. // is present if (a.ContainsKey(i)) { a[i] = a[i] + 1; } else { a.Add(i, 1); } } foreach (char j in t.ToCharArray()) { // Checking if the element of s is // present in t or not if (a.ContainsKey(j)) { // If present then decrease the // no. in map by 1 a[j] = a[j] - 1; } else { // If not present // increase count by 1 count++; } } Console.Write(count); // Return count return count; } // Driver Code public static void Main(String[] args) { String s = "ddcf", t = "cedk"; minSteps(s, t); }}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to count the minimum changes // to make the 2 strings anagram function minSteps(s, t) { let a = new Map(); // For counting the steps to be changed let count = 0; for (let i of s) { // Increasing the count if the no. // is present if (a.has(i)) { a.set(i, 1) } else { a.set(i, a.get(i) + 1) } } for (let j of t) { // Checking if the element of s is // present in t or not if (a.has(j)) { // If present then decrease the // no. in map by 1 a.set(j, a.get(j) - 1); } else { // If not present // increase count by 1 count++; } } document.write(count); // Return count return count; } // Driver Code let s = "ddcf", t = "cedk"; minSteps(s, t); // This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
