Minimum characters to delete to make string anagram

An algorithm to find the minimum characters to be removed to make two strings anagram.

We will implement a simple algorithm in javascript to find the minimum characters to be removed to make two string anagram. Everything will be written in ES6.

Note: Here we will be using lowercase alphabets in the string.

Example

Input:
'abc'
'cde'

'ghj'
'jhk'

Output:
// delete a and b from abc 
// delete d and e from cde
4

//delete g from ghj
//delete k from jhk
2

Implementation

• We will keep track of the characters occurrences in both the string.
• If the a character is present in both the string then we will reduce its count from both the tracker else we will return the combined count of the both trackers.

let makeAnagram = (a, b) => {
    //keep track of the characters count
    let countA = 0;
    let countB = 0;

    //Create an array of all the alphabets to monitor the occurrences
    let arr = new Array(26);
    arr.fill(0, 0, 26);
    
    //count the characters in the first string
    for (let i = 0; i < a.length; i++){
        arr[a[i].charCodeAt() - 'a'.charCodeAt()]++;
        countA++;
    }
    

    //count the characters in the second string
    for (let i = 0; i < b.length; i++){

        //if character is present in both the string then reduce it counts
        if (arr[b[i].charCodeAt() - 'a'.charCodeAt()]) {
            arr[b[i].charCodeAt() - 'a'.charCodeAt()]--;
            countA--;
        } else {
            countB++;
        }
    }
    
    //return the combined count of the characters
    return countA + countB;

}

Input:
console.log(makeAnagram('abc', 'cde'));
console.log(makeAnagram('ghj', 'jhk'));

Output:
4
2

The charCodeAt() function returns the ASCII value of the character. ASCII value of a is 97 and ASCII value of b is 98 so 98 - 97 = 1. Then array at index 1 will be incremented or decremented.

Time complexity: O(m + n).
Space complexity: O(1).

Time and space complexity

• We are iterating through both given strings and their lengths can vary, so Time complexity is (m + n) where m is the length of first string and n is the length of the second string.
• We are using an array of 26 lengths and it will not grow no matter what is the length of the strings i.e we are using constant space, so Space complexity is O(1).