 # Most Common Word solution using TypeScript

Below is my TypeScript solution to the LeetCode "Most Common Word" question.

Algorithm: This solution finds the most common word while only needing to iterate over each character in the paragraph once.

• Create a Set from the banned words array. This adds O(m) time complexity, but allows for O(1) lookups on banned words.
• Create a Set of invalid characters.
• Create a Hash Map of encountered words with a value reflecting how many times the given word has occurred.
• Create a pointer at the beginning of the paragraph and iterate over each character.
• If a character is valid, add it to a word buffer, and move on to the next character.
• If a character is invalid or whitespace, consider what is in the buffer a word. Update the Hash Map to reflect the additional occurrence of that word then reset the buffer.
• Return the word that occurred the most.

Time Complexity: The solution creates a Set of all banned words, which takes O(m) time, where m represents the number of banned words. It also iterates over each character in the inputted string exactly one time, which takes O(n) time, where n represents each character in the string. This results in an overall time complexity of O(m + n).

Space Complexity: The solution creates a Set of all banned words, which will take O(m) space, where m represents each banned word in the array. It also creates a Hash Map of each encountered word, which will take O(n) space where n represents each character in the inputted string. This results in an overall space complexity of O(m + n).

``````/**
* Most Common Word
* Given a paragraph and a list of banned words, return
* the most frequent word that is not in the list of
* banned words. It is guaranteed there is at least
* one word that isn't banned, and that the answer is unique.
*
* Words in the list of banned words are given in lowercase,
* and free of punctuation.  Words in the paragraph are not
* case sensitive.  The answer is in lowercase.
*
* Time Complexity: O(m + n)
* Space Complexity: O(m + n)
*
* mostCommonWord('foo foo bar', []) // 'foo'
* mostCommonWord('Foo, Bar BAR!', []) // 'bar'
* mostCommonWord('foo foo bar', ['foo']) // 'bar'
*/
function mostCommonWord(paragraph: string, bannedWords: string[]): string {
let invalid = new Set(["!","?","'",",",";","."," "]);
let banned = new Set(bannedWords);
let words = new Map();
let buffer = ""
let result = "";

for(let ptr = 0; ptr < paragraph.length; ptr++) {
// character is valid, append it to the buffer
if (!invalid.has(paragraph[ptr])) {
buffer += paragraph[ptr].toLowerCase();
// unless it is the last character, end this iteration
if (ptr !== paragraph.length - 1) {
continue;
}
}

// character is invalid or is the last one
if (buffer) {
// if the word is not banned, increment it's count
if (!banned.has(buffer)) {
let occurrences = (words.get(buffer) || 0) + 1;
let mostOccurrences = (words.get(result) || 0);
words.set(buffer, occurrences);
if (occurrences > mostOccurrences) {
result = buffer;
}
}
buffer = "";
}
}
return result;
};
``````

## more LeetCode posts Design HashSet solution using TypeScript Fizz Buzz solution using TypeScript Pascal's Triangle solution using TypeScript Min Stack solution using TypeScript Symmetric Tree solution using TypeScript Same Tree solution using TypeScript