Most common word that is not on a banned list — interview question

A feedback form collects free text. Find the most frequent word that is not on a banned list.

A word is a run of letters a–z/A–Z. Comparison is case-insensitive.
Banned words are given in lowercase.
If several words tie, print the one that appears first in the text.
Print the word in lowercase, followed by its count.

Constraints

0 ≤ b ≤ 50
The text has at most 20000 characters and at least one allowed word.

Input and output

Input: First line: b, then b banned words. The remaining lines are the text.
Output: One line: `word count`.

Examples

Input 1

2 the a
The mess food is fine. The mess timings are not;
the library is open.

Output

mess 2

"the" is banned. "mess" and "is" both appear twice; "mess" comes first in the text.

Input 2

0
Lab lab LAB notes

Output

lab 3

No banned words. Case is ignored, so "lab" appears 3 times.

Show hints

re.findall(r"[a-z]+", text.lower()) gives the words in order.
Put the banned words in a set for O(1) lookups.
collections.Counter counts them, but think about how to break ties by first appearance.

Show the explanation

Python

words = re.findall(r"[a-z]+", text.lower())
counts = Counter(w for w in words if w not in banned)
best = max(counts, key=counts.get)

Why the tie-break works: since Python 3.7, a dict (and so a Counter) remembers insertion order, so its keys come out in order of first appearance. max returns the first maximal element it meets, which gives exactly the "earliest in the text" rule. Counter.most_common(1) has the same tie behaviour, but max with an explicit key states the intent better.

Points to mention

Store banned as a set. Checking w in list is O(b) per word, while a set is O(1) on average.
Lower-case before the regex. Otherwise [a-z]+ splits Wifi into ifi.
The total cost is O(L) for L characters of text.
Without Counter, a plain dict with d[w] = d.get(w, 0) + 1 works the same way.

Original UniCircle question. Last reviewed 22 Oct 2026.