An autocomplete service wants to know, for a popular query, how often each of its prefixes appears inside the query itself, to tune suggestions.
Write prefixCounts(query) that returns an array counts of length n, where counts[L - 1] is the number of positions where query.slice(0, L) occurs in query (overlaps allowed). The prefix itself at position 0 counts, so every entry is at least 1.
Queries can be 100,000 characters long; checking each prefix separately is too slow.
Input: query = "abab" Output: [2,2,1,1]
a and ab each appear twice; aba and abab once.
Input: query = "aaa" Output: [3,2,1]
a three times, aa twice, aaa once.
1 <= query.length <= 10^5query contains lowercase letters.Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #621 How Often Each Prefix Appears. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.