What optimizations could be applied to reduce the execution time of finding min no. of steps to convert a string into an anagram of a given string?

Question

This requirement is a part of an algorithmic challenge. The details are as below:

Use Case/Requirement : Two strings viz. 's' & 't' consisting of only lowercase English alphabets & equal length have been given. The string 't' needs to be modified into an anagram of string 's' by replacing the characters in 't'. Every single replacement counts to be a single step. The expected output should be the minimum number of such steps required.

Example

Sample Input :

s = "friend"

t = "family"

Expected Output : 4

Reason : replace 'a', 'm', 'l' & 'y' by 'r', 'e', 'n' & 'd' in any order

My Approach

Data Structure Used : Hashing concept has been used & HashMap is being taken to create a roster for all the alphabets and their frequencies in the given strings

Algorithm Overview : First a map of the alphabet(s) and their frequencies is created for both the strings. Then the sum of the difference between the frequencies of common alphabets and the frequencies of the alphabets missing in the string 't' which are present in string 's' is calculated. Since the sum is twice of the required number of steps, the final answer is divided by 2 and returned as the solution.

FYR my code :

package com.task;

import java.util.Map;
import java.util.HashMap;
import java.util.Scanner;

class Solution {

    Map<Character, Integer> createFreqMap(String s) {
        char[] arr = s.toCharArray();
        Map<Character, Integer> m = new HashMap<>();
        for(char c : arr) {
            m.put(c, m.getOrDefault(c, 0) + 1);
        }
        return m;
    }

    int diffMap(Map<Character, Integer> ms, Map<Character, Integer> mt) {
        int d = 0;
        // traverse first map for diff
        for(Character c : ms.keySet()) {
            if(mt.containsKey(c)) {
                d += (Math.abs(ms.get(c) - mt.get(c)));
            }
            else d += ms.get(c);
        }

        // traverse second map for diff
        for(Character c : mt.keySet()) {
            if(!ms.containsKey(c)) {
                d += mt.get(c);
            }
        }
        return d;
    }

    public int minSteps(String s, String t) {
        Map<Character, Integer> sFreqMap = createFreqMap(s);
        Map<Character, Integer> tFreqMap = createFreqMap(t);
        int d = diffMap(sFreqMap, tFreqMap);
        return (d/2);
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.nextLine();
        String t = scan.nextLine();
        Solution obj = new Solution();
        System.out.println(obj.minSteps(s, t));
    }
}

The code works fine and gives me the desired solution, however it is slow as compared to the other participants, so how can the execution time be reduced in this?

Answer 1

First of all you don't need to traverse second map.

To further optimize this, you can use array instead of map. You only have 26 possible keys, so there won't be any memory problems.

public class App {

    int[] createFreqMap(String s) {
        char[] arr = s.toCharArray();
        int[] m = new int[26];
        for (char c : arr) {
            m[c - 'a']++;
        }
        return m;
    }

    int diffMap(int[] ms, int[] mt) {
        int d = 0;
        for (int i = 0; i < ms.length; i++) {
            d += Math.abs(ms[i] - mt[i]);
        }
        return d/2;
    }

    public int minSteps(String s, String t) {
        int[] sFreqMap = createFreqMap(s);
        int[] tFreqMap = createFreqMap(t);
        return diffMap(sFreqMap, tFreqMap);
    }

    public static void main(String[] args) {
        String s = "friend";
        String t = "family";
        App obj = new App();
        System.out.println(obj.minSteps(s, t));
    }
}