LeetCode 819: Most Common Word — Simple Explanation with Carry Logic (Java)

Difficulty: Easy

Topics: Array, Math, Hash Table, String, Counting

Platform: Leetcode

Problem Statement

Given a string paragraph and a string array of the banned words banned, return the most frequent word that is not banned. It is guaranteed there is at least one word that is not banned, and that the answer is unique.

The words in paragraph are case-insensitive and the answer should be returned in lowercase.

Note that words can not contain punctuation symbols.

Problem Statement Simplified
If in the paragraph string have the word in banned array, then discard it. If the paragraph string have ‘.’ or ‘ ’ then remove it. Make everything lowercase. Then give back the word that is most frequent.

Mistakes and Learning
Forgetting about removing ‘.’ or ‘ ’.
Look out for rare cases (ex:[a.])

Example 1

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation:
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph.
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"),
and that "hit" isn't the answer even though it occurs more because it is banned.

Example 2

Input: paragraph = "a.", banned = []
Output: "a"

Key Insight

Initialize a HashMap and HashSet for paragraph String and banned array.
If not a word from banned array then add to HashMap and increment the counter
If a word from banned array then move to next word.

Algorithm

1. Remove everything from string other than [a-z] and make it lowercase.
2. Initialize a String array and add the string words to it using split function.
3. Initialize HashMap and HashSet for string array and banned word array respectively.
4. Initialize an int max and string maxWord to check and return the max repeating word.
5. Initialize a for loop and add the banned array to HashSet. end for loop
6. Initialize a for loop.
7. Store the current word in String array to a string.
8. If not a word in HashSet.
9. Put in HashMap and increment the value if not already present.
10. If value is greater than max.
11. Assign the value to max.
12. Assign word to maxWord.
13. end if.
14. end if
15. end for loop.
16. return max word.

Algorithm in simple words

First, remove everything from string other than [a-z] and make it lowercase. Then split the string and store it in an array.
Initialize a HashMap to store the string and integer - so that we can just look at this hashmap and check how many times the string repeated. everytime we loop through the string array (we created earlier), we will store the words in hashmap and assign a value to it which will increment when the word is repeated in the array.

Initialize a HashSet to store the string — so that the banned word array can be stored and compared with hashmap.

Initialize an int max and string maxWord to check and return the max repeating word.

Initialize a for loop which will go thorugh the banned words array and add them to HashSet.

Then we will loop through the string array and check the HashSet and current word from String array. If same then we will move to next word from String array. If not then we will add it to HashMap and if the word already exists then we will increment the value of it ( using map.getOrDefault(word,0) it will return the current value, if the word doesnt exists then it wil return 0 otherwise the current value of that word from HashMap ).

Then we will check of this value is greater than max, if yes then we will set this value as new max and this word as new maxWord.

Java code

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        paragraph= paragraph.toLowerCase().replaceAll("[^a-z]"," ");
        String[] words= paragraph.split("\\s+");
        Map<String,Integer> map= new HashMap<>();
        Set<String> bannedWord=new HashSet<>();
        int counter=0;
        int max=-1;
        String maxWord="";
        for (int i=0;i<banned.length;i++){
            bannedWord.add(banned[i].toLowerCase());
        }
        for(int i=0;i<words.length;i++){
             String word=words[i];
            if(!bannedWord.contains(word)){
            map.put(word,map.getOrDefault(word,0)+1);

            if(map.get(word)>max){
                max=map.get(word);
                maxWord=word;
            }
            }
        }
        return maxWord;

    }
}

Time & Space Complexity

Time Complexity: O(n+m)

Space Complexity: O(n+m)