Introduction

In this blog post, we will explore how to solve the LeetCode problem "819" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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. 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" Constraints: 1 <= paragraph.length <= 1000 paragraph consists of English letters, space ' ', or one of the symbols: "!?',;.". 0 <= banned.length <= 100 1 <= banned[i].length <= 10 banned[i] consists of only lowercase English letters.

Explanation

• Preprocessing: Convert the paragraph to lowercase and remove punctuation.
  • Word Counting: Use a hash map to count the frequency of each word.
  • Filtering and Maximization: Iterate through the word counts, excluding banned words, and find the word with the highest frequency.

• Runtime Complexity: O(N + M), where N is the length of the paragraph and M is the number of banned words. Storage Complexity: O(N + B), where N is the number of unique words in the paragraph and B is the number of banned words.

Code

    import re
from collections import defaultdict

def mostCommonWord(paragraph: str, banned: list[str]) -> str:
    """
    Finds the most frequent word in a paragraph that is not in the banned list.

    Args:
        paragraph: The input paragraph.
        banned: A list of banned words.

    Returns:
        The most frequent non-banned word in lowercase.
    """

    # 1. Preprocessing: Remove punctuation and convert to lowercase
    paragraph = re.sub(r"[!?',;.]", " ", paragraph).lower()
    words = paragraph.split()

    # 2. Word Counting: Count word frequencies
    word_counts = defaultdict(int)
    for word in words:
        word_counts[word] += 1

    # 3. Filtering and Maximization: Find the most frequent non-banned word
    banned_set = set(banned)  # Convert banned list to a set for faster lookup
    max_count = 0
    most_common = ""

    for word, count in word_counts.items():
        if word not in banned_set and count > max_count:
            max_count = count
            most_common = word

    return most_common