If you're working with small strings, there isn't any need to complicate things. The following method is simple, at the expense of performance when dealing with very large strings.
First we need to define an object to hold the counts for our duplicate characters.
Then we need to iterate each string. There are many way of going about iterating a string, but in the following examples I either:
Both of these methods work because a string is an example of a built-in iterable object.
While iterating the strings, we need to first check if the character exists in the duplicate object.
- If it does, we don't need to check it again, just increment the number.
- If it does not, scan the other string to see if the character occurs there.
- If it does, increment the duplicate counter for that character.
- If it does not, do nothing.
Using this method, you don't count characters that aren't duplicates, and you don't try to verify characters that you have already verified. This should offer some significant speed improvements with longer strings.
Once you have finished iterating both strings, simply return the duplicate holder object.
ES6 Example
const countLetters = (v1, v2) => {
const out = {};
for(let char of v1) (out[char] || v2.indexOf(char) !== -1) && (out[char] = (out[char] || 0) + 1);
for(let char of v2) (out[char] || v1.indexOf(char) !== -1) && (out[char] = (out[char] || 0) + 1);
return out;
}
const test = (v1,v2) => (console.log(JSON.stringify(countLetters(v1, v2))),test);
test("Leopard", "Lion") // { "L": 2, "o": 2 }
("Hello", "World") // { "l": 3, "o": 2 }
("Flower", "Power") // { "o": 2, "w": 2, "e": 2, "r": 2 }
("phone", "Memphis") // { "p": 2, "h": 2, "e": 2 }
("Bookkeeper", "Zookeeper") // { "o": 4, "k": 3, "e": 6, "p": 2, "r": 2 }
("Some thing", "Other thing"); // { "e": 2, " ": 2, "t": 3, "h": 3, "i": 2, "n": 2, "g": 2 }
ES5 Example
var countLetters = function(v1, v2) {
var out = {};
Array.prototype.forEach.call(v1, function(char) {
if(out[char] || v2.indexOf(char) !== -1) out[char] = (out[char] || 0) + 1;
});
Array.prototype.forEach.call(v2, function(char) {
if(out[char] || v1.indexOf(char) !== -1) out[char] = (out[char] || 0) + 1;
});
return out;
}
var test = function(v1,v2){ return (console.log(JSON.stringify(countLetters(v1, v2))),test) };
test("Leopard", "Lion") // { "L": 2, "o": 2 }
("Hello", "World") // { "l": 3, "o": 2 }
("Flower", "Power") // { "o": 2, "w": 2, "e": 2, "r": 2 }
("phone", "Memphis") // { "p": 2, "h": 2, "e": 2 }
("Bookkeeper", "Zookeeper") // { "o": 4, "k": 3, "e": 6, "p": 2, "r": 2 }
("Some thing", "Other thing"); // { "e": 2, " ": 2, "t": 3, "h": 3, "i": 2, "n": 2, "g": 2 }
Performance becomes a concern when you start working with very large strings. The following method employs some algorithmic wizardry to gain performance.
First, find the frequency of each letter in both strings. Working with a sorted array is faster than working with an unsorted array, and saves some time counting because we can split the string into groups of common characters instead of counting each character.
I use a Map
object to take advantage of the Map#has
method—which is much faster than Array#indexOf
—in the next function.
// Calculate the frequency of each character in a string
const calculateCharacterFrequency = string => {
// Split the string into individual characters
const array = [...string];
// Sort the split string
const sorted = array.sort();
// Join the split string
const joined = sorted.join("");
// Split the string into groups of common characters
const matches = joined.match(/(.)\1*/g);
// Iterate the groups
const frequency = matches.reduce(
(frequency, character) => {
// Insert char and frequency into map
frequency.set(character[0], character.length);
// return frequency map for use in next iteration
return frequency;
},
// This is the map that will be passed as `frequency`
new Map()
);
// Return the map
return frequency;
};
Next, find the common characters between each string and create a map containing the frequency of each common character.
The biggest performance gain here is to create a unique set of all of the characters that occur in either string. I utilize the unique nature of a Set
object to remove duplicates from the array, there are other ways of going about removing duplicates from an array but that was the fastest one that I tested. This way, we are only iterating one unqiue set and checking that the character occurs in both maps.
// Calculate the frequency of each character two strings have in common
const calculateCommonCharacterFrequency = (v1, v2) => {
// Get frequency map of first string
v1 = calculateCharacterFrequency(v1);
// Get frequency map of second string
v2 = calculateCharacterFrequency(v2);
// Create an array containing a list of all characters occuring in either string
const combinedCharacterArray = [...v1.keys(), ...v2.keys()];
// Remove duplicate characters
const combinedUniqueCharacterSet = new Set(combinedCharacters);
// Convert set back to array
const combinedUniqueCharacterArray = Array.from(combinedUniqueSet);
// Iterate the unique array of common characters
const commonFrequency = combinedUniqueCharacterArray.reduce(
(commonFrequency, character) => {
// Check if both strings have the character
const isCommon = v1.has(character) && v2.has(character);
if(isCommon) {
// Find the sum of the frequency of the character in both strings
const combinedFrequency = v1.get(character) + v2.get(character);
// Insert character and frequency into map
commonFrequency.set(character, combinedFrequency);
}
// return frequency map for use in next iteration
return commonFrequency;
},
// This is the map that will be passed as `commonFrequency`
new Map()
);
// Return the map
return commonFrequency;
};
Condensed Example
The above example has been expanded for readability and explanation purposes. The following example has been condensed to save space.
const calcCharFreq = string => [...string].sort().join("").match(/(.)\1*/g).reduce((freq, char) => (freq.set(char[0], char.length), freq), new Map());
const calcCommonCharFreq = (v1, v2) => {
v1 = calcCharFreq(v1);
v2 = calcCharFreq(v2);
return Array.from(new Set([...v1.keys(), ...v2.keys()])).reduce((dup, char) => ((v1.has(char) && v2.has(char)) && dup.set(char, v1.get(char) + v2.get(char)), dup), new Map());
};
const test = (v1,v2) => (console.log('{ '+Array.from(calcCommonCharFreq(v1, v2)).reduce((pairs, value) => (pairs.push('"'+value[0]+'": '+value[1]), pairs), []).join(", ")+' }'), test);
test("Leopard", "Lion") // { "L": 2, "o": 2 }
("Hello", "World") // { "l": 3, "o": 2 }
("Flower", "Power") // { "o": 2, "w": 2, "e": 2, "r": 2 }
("phone", "Memphis") // { "p": 2, "h": 2, "e": 2 }
("Bookkeeper", "Zookeeper") // { "o": 4, "k": 3, "e": 6, "p": 2, "r": 2 }
("Some thing", "Other thing"); // { "e": 2, " ": 2, "t": 3, "h": 3, "i": 2, "n": 2, "g": 2 }