Solution For Minimum Number Of Steps To Make Two Strings Anagram

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.

Step by Step Implementation For Minimum Number Of Steps To Make Two Strings Anagram

class Solution { 
    public int minSteps(String s, String t) { 
        int[] count = new int[26]; 
  
        for (int i = 0; i < s.length(); i++) 
            count[s.charAt(i) - 'a']++; 
  
        for (int i = 0; i < t.length(); i++) 
            count[t.charAt(i) - 'a']--; 
  
        int result = 0; 
        for (int i = 0; i < 26; i++) 
            result += Math.abs(count[i]); 
  
        return result / 2; 
    } 
}

def minSteps(s, t):
    
    # initialize a dictionary to keep track of the number of each character in s
    s_dict = {}
    
    # initialize a variable to keep track of the minimum number of steps
    min_steps = 0
    
    # loop through s to populate the dictionary
    for char in s:
        if char in s_dict:
            s_dict[char] += 1
        else:
            s_dict[char] = 1
    
    # loop through t
    for char in t:
        
        # if the current character is not in the dictionary, that means we need to add
        # it to s, so we increment the minimum number of steps
        if char not in s_dict:
            min_steps += 1
        
        # otherwise, we decrement the count for that character in the dictionary
        else:
            s_dict[char] -= 1
            
            # if the count for that character is now negative, that means we need to 
            # remove it from s entirely, so we increment the minimum number of steps
            if s_dict[char] < 0:
                min_steps += 1
    
    # return the minimum number of steps
    return min_steps

var minSteps = function(s, t) {
    // create a hashmap to store the count of each character in string s
    let sCharMap = {};
    for (let i = 0; i < s.length; i++) {
        // if the character is not in the hashmap, set the count to 1
        if (!(s.charAt(i) in sCharMap)) {
            sCharMap[s.charAt(i)] = 1;
        // if the character is already in the hashmap, increment the count by 1    
        } else {
            sCharMap[s.charAt(i)]++;
        }
    }
    
    // create a hashmap to store the count of each character in string t
    let tCharMap = {};
    for (let i = 0; i < t.length; i++) {
        // if the character is not in the hashmap, set the count to 1
        if (!(t.charAt(i) in tCharMap)) {
            tCharMap[t.charAt(i)] = 1;
        // if the character is already in the hashmap, increment the count by 1    
        } else {
            tCharMap[t.charAt(i)]++;
        }
    }
    
    // initialize a count variable to keep track of the number of steps needed
    let count = 0;
    
    // iterate through all the keys in the sCharMap
    for (let key in sCharMap) {
        // if the key is not in the tCharMap, that means we need to delete all occurrences of that character from s
        // so we add the count of that character to our count variable
        if (!(key in tCharMap)) {
            count += sCharMap[key];
        // if the key is in the tCharMap, that means we need to delete the extra occurrences of that character from s    
        } else {
            // we only need to delete the extra occurrences, so we take the difference of the counts of that character in both strings and add it to our count variable
            count += Math.abs(sCharMap[key] - tCharMap[key]);
        }
    }
    
    // iterate through all the keys in the tCharMap
    for (let key in tCharMap) {
        // if the key is not in the sCharMap, that means we need to delete all occurrences of that character from t
        // so we add the count of that character to our count variable
        if (!(key in sCharMap)) {
            count += tCharMap[key];
        }
    }
    
    // return the count variable
    return count;
};

int minSteps(string s, string t) 
{
    int n = s.length();
    int m = t.length();
    int ans = 0;
    
    // If one string is empty, we need to insert all characters of other string
    if(n == 0)
        return m;
    if(m == 0)
        return n;
        
    // We can consider each character of one string as extra character and find minimum 
    // insertions needed for the second string
    for(int i = 0; i < n; i++)
    {
        int j;
        for(j = 0; j < m; j++)
            if(s[i] == t[j])
                break;
                
        // If all characters of second string are not present in first, 
        // then we need to insert those characters
        if(j == m)
            ans += n-i;
    }
    
    return ans;
}

public int MinSteps(string s, string t) { int steps = 0; // Keep track of how many characters need to be changed Dictionary counts = new Dictionary(); foreach(char c in s) { if(!counts.ContainsKey(c)) { counts[c] = 0; } counts[c]++; } foreach(char c in t) { if(!counts.ContainsKey(c)) { counts[c] = 0; } counts[c]--; } // Count the number of characters that need to be changed foreach(int count in counts.Values) { steps += Math.Abs(count); } return steps / 2; }