Minimum Number Of Steps To Make Two Strings Anagram - Leetcode Solution

Problem:

Given two equal-length strings s and t. In one step you can choose any character of t and replace it with another character.

Return the minimum number of steps to make t an anagram of s.

Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "bab", t = "aba" Output: 1 Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.

Example 2:

Input: s = "leetcode", t = "practice" Output: 5 Explanation: Replace 'p', 'r', 'a', 'c' and 'e' from 'practice' with 'd', 'o', 't', 'e' and 'c' respectively. Now t = "leetcode" which is anagram of s.

Solution:

We can solve this problem by using a hash map. We can count the frequency of each character in both strings s and t. Then, we can get the absolute difference between the frequency of each character in both strings. The sum of these differences will give us the minimum number of steps required to make t an anagram of s.

Steps:

1. Create a hashmap h with characters as keys and values as integers.

2. Iterate through the string s and increment the value of h[c] for each character c.

3. Iterate through the string t and decrement the value of h[c] for each character c.

4. Iterate through the keys of the hashmap h and add the absolute value of h[c] to a variable count.

5. Return count/2, as we need to do count/2 replacements to make t an anagram of s.

Code:

class Solution { public int minSteps(String s, String t) { int[] count = new int[26]; int n = s.length(); for(int i=0; i<n; i++) { count[s.charAt(i)-'a']++; count[t.charAt(i)-'a']--; } int res = 0; for(int i=0; i<26; i++) { if(count[i]>0) { res += count[i]; } } return res; } }

Time Complexity: O(n), where n is the length of the input strings s and t.

Space Complexity: O(1), as we are using a constant sized array to store the frequency of characters.

1