Detect disguised abusive words in comments

Question: Detect disguised abusive words in comments

Companies: Amazon

Difficulty: Hard

Problem statement

A comment platform wants to catch abusive words that users disguise with look-alike characters, such as $ for s or 0 for o.

Implement AbuseDetector:

• AbuseDetector(banned, substitutions): banned is a list of lowercase words. substitutions maps a disguise character to the letters it can stand for, as a string. One character can stand for several letters, for example "1": "il".
• detect(comment) -> List[str]: returns the banned words found in the comment, in order of appearance.
• flag(comments) -> List[int]: returns the indices of comments that contain at least one banned word.

Rules

• Matching is case-insensitive.
• A token is a maximal run of characters that are letters, digits, or disguise characters. Every other character separates tokens.
• A token matches a banned word when the whole token can spell it, reading each character either as itself (if it is a letter) or as one of the letters it can stand for. A banned word inside a longer token does not count.

Constraints

• Up to 10^5 banned words with total length up to 10^6.
• Comments up to 10^4 characters. A character can stand for up to 3 letters.

Example

banned = ["jerk", "idiot", "loser"]
substitutions = {"$": "s", "0": "o", "3": "e", "!": "i", "1": "il", "|": "il"}

detect("What an !d!0t, honestly. J3RK.")  ->  ["idiot", "jerk"]
detect("|0$3r")                            ->  ["loser"]
detect("jerky snacks")                     ->  []
flag(["great post", "j3rk", "l0ser!"])     ->  [1]

In the last call, ! is a disguise character, so l0ser! is one token. It spells loseri, which is not banned.

Part 2. Users also stretch words, as in jeeeerk or l0000ser. Add an option where each letter of a banned word may appear one or more times in a row. Interviewers may then ask about separators inside words (j.e.r.k), banned words inside longer tokens, and multi-character disguises such as |< for k.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

Clarify first. You get a list of banned words and a substitution table that says which disguise characters can stand for which letters (@ for a, $ for s, 1 for i or l, and so on). A comment is split into tokens, and a token is flagged when it spells a banned word as a whole, after each character is read as itself or as one of the letters it can stand for. Ask: is matching case-insensitive (yes)? Is the whole token matched, or any substring (whole token, so jerky is fine)? Can one disguise character stand for several letters (yes, 1 can be i or l)? What separates tokens? Here, any character that is not a letter, a digit, or a disguise character. That way ! can be part of !d!0t but a comma ends a token.

Brute force. For each token, expand every disguise character into all of its letters and check each resulting spelling against a set of banned words. A token with m ambiguous characters, each with up to b readings, has b^m spellings. This is fine for short tokens but blows up on something like 1111111111. A second brute force is to compare each token against each banned word character by character. That costs O(W * L) per token for W banned words, which is slow when the list has many thousands of words.

Optimal: walk a trie with a set of states. Put the banned words in a trie. Read the token one character at a time and keep the set of trie nodes the prefix read so far can reach. For each character, every node in the set moves to its child for every letter the character can stand for. If the set becomes empty, stop early: no banned word fits. At the end, the token matches if any node in the set ends a banned word.

Why it works. Invariant: after reading k characters, the set holds exactly the trie nodes whose path spells a letter string that the first k characters can represent. Reading one more character extends each of those strings by each allowed letter, which is the child step. The set never holds more than one entry per trie node, so the ambiguity is merged instead of multiplied. This is the same idea as simulating an NFA by tracking its set of active states.

Repeated letters (part 2). Users also stretch words, as in jeeeerk. Allow a character to stay on the current node when it can stand for that node's own letter. That one extra transition handles any number of repeats and still keeps one entry per node.

Code

from __future__ import annotations


from dataclasses import dataclass, field


@dataclass
class TrieNode:
    letter: str = ""
    children: dict[str, "TrieNode"] = field(default_factory=dict)
    word: str | None = None  # set when a banned word ends here


class AbuseDetector:
    def __init__(
        self,
        banned: list[str],
        substitutions: dict[str, str],
        allow_repeats: bool = False,
    ) -> None:
        self.root = TrieNode()
        for w in banned:
            node = self.root
            for ch in w.lower():
                node = node.children.setdefault(ch, TrieNode(letter=ch))
            node.word = w.lower()
        # disguise character -> letters it may stand for
        self.subs = {k.lower(): set(v.lower()) for k, v in substitutions.items()}
        self.allow_repeats = allow_repeats

    def _candidates(self, ch: str) -> set[str]:
        c = ch.lower()
        letters = set(self.subs.get(c, ()))
        if c.isalpha():
            letters.add(c)
        return letters

    def _is_token_char(self, ch: str) -> bool:
        return ch.isalnum() or ch.lower() in self.subs

    def tokens(self, comment: str) -> list[str]:
        out: list[str] = []
        cur: list[str] = []
        for ch in comment:
            if self._is_token_char(ch):
                cur.append(ch)
            elif cur:
                out.append("".join(cur))
                cur = []
        if cur:
            out.append("".join(cur))
        return out

    def match_token(self, token: str) -> str | None:
        """Return the banned word this whole token can spell, else None."""
        nodes: dict[int, TrieNode] = {id(self.root): self.root}
        for ch in token:
            letters = self._candidates(ch)
            nxt: dict[int, TrieNode] = {}
            for node in nodes.values():
                for letter in letters:
                    child = node.children.get(letter)
                    if child is not None:
                        nxt[id(child)] = child
                if self.allow_repeats and node is not self.root and node.letter in letters:
                    nxt[id(node)] = node  # "asss": stay on the same letter
            if not nxt:
                return None
            nodes = nxt
        hits = sorted(n.word for n in nodes.values() if n.word is not None)
        return hits[0] if hits else None

    def detect(self, comment: str) -> list[str]:
        """Banned words found in the comment, in order of appearance."""
        found: list[str] = []
        for tok in self.tokens(comment):
            w = self.match_token(tok)
            if w is not None:
                found.append(w)
        return found

    def flag(self, comments: list[str]) -> list[int]:
        """Indices of comments that contain at least one banned word."""
        return [i for i, c in enumerate(comments) if self.detect(c)]

Complexity

Let S be the total length of all banned words, n the comment length, b the largest number of letters one character can stand for, and A the largest number of trie nodes active at once.

• Build: O(S) time and space for the trie, plus O(size of the table).
• match_token(token): O(len(token) * A * b) time. A is at most the number of trie nodes at one depth, and in practice it is small, because real disguise tables are sparse. Without ambiguity A = 1, so the cost is linear. Space O(A).
• detect(comment): O(n * A * b) time, O(n) space for the tokens.
• flag(comments): the sum over all comments. The trie is shared, so the banned list is never rescanned.

Test cases

With subs = {"@": "a", "4": "a", "$": "s", "5": "s", "0": "o", "1": "il", "!": "i", "3": "e", "|": "il"} and banned words ["jerk", "idiot", "loser"]:

• "You are an !d!0t, total J3RK." gives ["idiot", "jerk"] (case-insensitive, comma and period split tokens).
• "l0$3r" gives ["loser"] (several substitutions in one token).
• "|0ser" gives ["loser"] (| can be i or l, and only l fits).
• "jerky snack" gives [] (whole-token match, not substring).
• "idiots" gives [].
• "" gives [].
• "jerk!" gives [], because ! is a disguise character and stays in the token. Say this design choice out loud.
• flag(["nice post", "j3rk", "loser.", "ok"]) gives [1, 2].
• With allow_repeats=True and banned ["jerk", "ass"]: "@$$$$ jeeeerk" gives ["ass", "jerk"]. "@s" gives [] (a repeat cannot replace a missing letter).
• With repeats off, "@ssss" does not match "ass".

Follow-ups

1. Stretched words (jeeeerk, @$$$$). Add the stay-on-node transition shown in the code. The state set still has at most one entry per node.
2. Separators inside a word (j.e.r.k, j e r k). Treat a small set of filler characters as skippable: on a filler, keep the current states unchanged. If spaces are fillers too, tokenization no longer works. Scan the whole comment with the state set, and start a new walk at every word boundary. To avoid false positives across real words (a ss), only allow fillers between single characters.
3. Banned words inside longer tokens (youjerk). Build an Aho-Corasick automaton over the banned words and run the same set-of-states walk over it. Each character still maps to several letters. Failure links let a match start anywhere, so the scan is still one pass over the comment. Add an allow-list (assistant, class) to avoid the Scunthorpe problem.
4. Multi-character disguises (|< for k, ph for f). Put the disguise strings in their own trie. At position i, every disguise that starts there moves the state set forward to position i + len(disguise). Keep a map from position to state set, which turns the walk into a DP over positions.
5. Scale: millions of comments a day. The detector is read-only after it is built, so share one instance across worker threads or processes. Normalize Unicode first (NFKC, then a confusables table for Cyrillic а vs Latin a). Cache results for repeated tokens with an LRU cache, since comment vocabularies are heavily skewed. Hot-reload the banned list by building a new trie and swapping the reference.

Interviewer expectations

Mid-level (L4)

• Asks how tokens are split and whether matching is whole-word, then writes a working matcher. A per-token expansion or a pairwise comparison is acceptable at first.
• Handles case, punctuation, and a character that maps to several letters.
• Gives correct complexity and tests the edge cases (empty comment, substring that should not match).

Senior (L5)

• Gets to the trie with a set of active states without hints and explains why it avoids the exponential expansion.
• Adds repeated letters or separators as a small change to the transition rule, not a rewrite.
• Discusses false positives (Scunthorpe problem) and proposes an allow-list.

Staff (L6+)

• Frames the matcher as an NFA over the banned-word trie, and extends it to substring matching with Aho-Corasick and to multi-character disguises with a position DP.
• Talks about the production system: Unicode normalization and confusables, hot reloading the word list, caching, throughput, and how this rule-based filter sits next to an ML classifier and human review.
• Names how to measure it: precision and recall on labeled comments, and how users adapt once a rule ships.