LeetCode - Strings - Minimum Number of Steps to Make Two Strings Anagram

Given two equal-size 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.

An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.

 

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', 'i' and 'c' from t with proper characters to make t anagram of s.
class Solution {
    public int minSteps(String s, String t) {
        if(t.equals(s)){
            return 0;
        }
        
        char s_sort[] = s.toCharArray();
        Arrays.sort(s_sort);
        String s_sorted = new String(s_sort);
        
        char t_sort[] = t.toCharArray();
        Arrays.sort(t_sort);
        String t_sorted = new String(t_sort);
        
        //System.out.println(s_sorted);
        //System.out.println(t_sorted);
        
        if(s_sorted.equals(t_sorted)){
            return 0;
        }
        
        int counter = 0;
        Map<String,Integer> s_map = getFreqMap(s);
        Map<String,Integer> t_map = getFreqMap(t);
        
        //System.out.println(s_map);
        //System.out.println(t_map);
        for(String s1: s_map.keySet()){
            if(t_sorted.contains(s1)){
                if(t_map.get(s1) < s_map.get(s1)){
                    counter = counter + s_map.get(s1) - t_map.get(s1);
                }
            }else{
                counter = counter + s_map.get(s1);
            }
        }
        return counter;
    }
    
    public Map<String,Integer> getFreqMap(String s){
        Map<String,Integer> freqMap = new TreeMap<String,Integer>();
        for(char c:s.toCharArray()){
            freqMap.put(c+"",freqMap.getOrDefault(c+"",0)+1);
        }
        return freqMap;
    }
}

Recent Updates

Recent updates on DevOpsPal

Social

Follow us of social for latest updates.

DevOps Hub

Links to get started.