Step 4: Unveiling the Duplicates
Identifying Duplicates Made Easy
After painstakingly counting the frequency of each word, finding duplicates becomes a cakewalk. All we have to do is sift through our occurrences
HashMap and pinpoint the words that have a frequency of 2
or more. These are our coveted duplicates.
Code Snippet for Identifying Duplicates
Here's how you can extract the duplicates from our occurrences
HashMap:
1let duplicates = [];
2for (let [word, count] of Object.entries(occurrences)) {
3 if (count > 1) {
4 duplicates.push(word);
5 }
6}
Analyzing the Complexity of Our Final Solution
Time Complexity Revisited
Let n
be the number of words in our input string s
.
- Populating the
occurrences
HashMap tookO(n)
time. - Traversing the
occurrences
HashMap to identify duplicates also takesO(n)
time.
Summing these up, our algorithm works in linear O(n)
time, which is remarkably efficient.
Space Complexity Revisited
We've used a HashMap (occurrences
) to store the frequency of each word, and a list (duplicates
) to store the duplicate words. In a worst-case scenario, each word in the sentence is unique, making our space complexity linear O(n)
.
xxxxxxxxxx
21
let s = "Original String Original String";
let split_s = s.toLowerCase().split(' ');
​
let occurrences = {};
​
for (let word of split_s) {
if (!occurrences[word]) {
occurrences[word] = 1;
} else {
occurrences[word] += 1;
}
}
​
let dupes = [];
for (let k in occurrences) {
if (occurrences[k] === 2) {
dupes.push(k);
}
}
​
console.log(dupes);
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment