LeetCode 1268 Search Suggestions System - Why Naive Fails

For each prefix, filter products that start with it, sort, and take the first 3.

With $n$ products and search word of length $m$, you filter $n$ products $m$ times: $O(m \cdot n)$.

Can you avoid rescanning all products for each prefix?