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.
Anagram: An anagram of a string is another string that contains same characters, only the order of characters can be different.
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).