Sum of Prefix Scores of Strings — Counted Trie Aggregation

Problem Statement#

LeetCode 2416 — Sum of Prefix Scores of Strings | Difficulty: Hard

You are given an array words of size n consisting of non-empty strings.

We define the score of a string term as the number of strings words[i] such that term is a prefix of words[i].

Return an array answer of size n where answer[i] is the sum of scores of every non-empty prefix of words[i].

Example:

Input:  words = ["abc","ab","bc","b"]
Output: [5, 4, 3, 2]
 
For "abc":
  prefix "a"   → 2 words start with "a"   ("abc","ab")
  prefix "ab"  → 2 words start with "ab"  ("abc","ab")
  prefix "abc" → 1 word  starts with "abc"("abc")
  total = 2 + 2 + 1 = 5

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] consists of lowercase English letters.

Why This Problem Matters#

Sum of Prefix Scores is the canonical "counted trie" interview question, asked at Amazon, Google, and Bloomberg. It is the bridge problem that elevates a candidate from "I can implement a trie" to "I understand why prefix tree augmentation is powerful." The naive O(N^2 times L) solution times out on the constraints, and only the trie-with-counter pattern hits the required O(N times L) budget.

The technique generalises immediately: the same trie-with-count primitive powers autocomplete ranking ("rank by popularity"), spelling correction, "longest popular prefix" scoring at Lucene, and FAANG search-suggestion services. Once you internalise this template, dozens of trie problems collapse to "insert with counter, walk to query."

The Core Insight#

For every prefix p, define count(p) = number of words that pass through the trie node for p. We can compute this for every prefix simultaneously by incrementing a counter at each node along the insertion path.

Then, for word w of length L, the answer is the sum of counters along its trie path — exactly count(w[0:1]) + count(w[0:2]) + ... + count(w[0:L]). That is L lookups, not O(N times L) comparisons.

The pattern is two-phase:

1. Build phase — for every word, walk the trie inserting characters. At each visited node, increment cnt.
2. Query phase — for every word, walk the trie again summing cnt along the path. Output the accumulated sum.

Both phases are O(N times L). No DP, no sorting, no extra data structures.

Visual Dry Run#

Words: ["abc", "ab", "bc", "b"]. After inserting all four with counter increments:

root
 |-- a (cnt=2)            ← "abc","ab" pass through
 |    |-- b (cnt=2)        ← "abc","ab" pass through
 |    |    |-- c (cnt=1)    ← only "abc" passes
 |
 |-- b (cnt=2)            ← "bc","b" pass through
      |-- c (cnt=1)        ← only "bc" passes

Now query each word by walking the trie and summing counters:

"abc": a(2) + b(2) + c(1) = 5
"ab" : a(2) + b(2)        = 4
"bc" : b(2) + c(1)        = 3
"b"  : b(2)               = 2

Output: [5, 4, 3, 2]. Each word's path-sum is the answer for that index.

Solution (Optimal) — Counted Trie#

Python#

class TrieNode:
    __slots__ = ("children", "cnt")
    def __init__(self):
        self.children = {}
        self.cnt = 0
 
class Solution:
    def sumPrefixScores(self, words: list[str]) -> list[int]:
        root = TrieNode()
        # Build phase: increment cnt at every node along each word's path
        for w in words:
            node = root
            for ch in w:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
                node.cnt += 1
        # Query phase: sum cnt along each word's path
        ans = []
        for w in words:
            node = root
            score = 0
            for ch in w:
                node = node.children[ch]
                score += node.cnt
            ans.append(score)
        return ans

JavaScript#

class TrieNode {
  constructor() {
    this.children = {};
    this.cnt = 0;
  }
}
 
var sumPrefixScores = function(words) {
  const root = new TrieNode();
  for (const w of words) {
    let node = root;
    for (const ch of w) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
      node.cnt++;
    }
  }
  const ans = [];
  for (const w of words) {
    let node = root, score = 0;
    for (const ch of w) {
      node = node.children[ch];
      score += node.cnt;
    }
    ans.push(score);
  }
  return ans;
};

Complexity#

• Build: O(N times L) — each character of each word visits one node and increments once.
• Query: O(N times L) — each word retraces its path summing counters.
• Space: O(N times L) for trie nodes (worst case, no shared prefixes).

Common Mistakes#

1. Forgetting to increment cnt at the root vs first child — increment only after moving into the child node, otherwise root's cnt becomes meaningless and inflates every score by N.
2. Counting at terminal nodes only — only words that end at that node would be counted. We need every passing word, so increment on every step.
3. Building two passes inside one loop — interleaving build and query produces wrong scores for words processed before all words are inserted.
4. Using a fixed-size array of 26 children for memory savings — fine, but ensure you initialise cnt to 0 (Python defaults work, JavaScript may give undefined).
5. Trying to compute via sorting + LCP — works but is O(N times L times log N) and harder to implement; trie is cleaner.
6. Misreading the problem as needing terminal count only — terminal count gives you "how many words equal this exact prefix," not "how many words start with it."

Interview Tips#

• Open by stating the brute force: "For each word, for each prefix, scan all other words — that is O(N^2 times L) and will TLE."
• Introduce the counted-trie pattern as "instead of repeating work per query, precompute count at each node during insert."
• Walk through the two-phase build-then-query split — interviewers love phase decomposition.
• State the invariant clearly: "After build, node p.cnt equals the number of words sharing prefix p."
• Mention that this same pattern handles "k-th most popular prefix," "all words sharing the most popular 3-letter prefix," and other autocomplete-ranking variants.

Follow-up Questions#

• Top-k most popular prefixes? Walk the trie BFS, push (node.cnt, prefix_string) into a min-heap of size k.
• Online updates (insert and query interleaved)? Maintain incremental counters; insertions still O(L), queries still O(L).
• Suffix scores instead? Reverse each word and apply the same algorithm — counted reverse trie.
• Weighted scores (each word has a weight)? Replace cnt += 1 with cnt += weight[w].
• Memory-constrained version? Compress to a Patricia (radix) trie for fewer nodes; counter still increments per word.

Key Takeaways#

• Counted trie augments each node with cnt = number of words passing through, computed in O(L) per insert.
• The score of any prefix equals the trie node's cnt — no scan, no comparison.
• Build-then-query separation makes both phases independently O(N times L).
• This single primitive powers autocomplete ranking, popular-prefix search, and FAANG search suggestion services.
• Watch for off-by-one at the root: increment only after stepping into the child node.
• Mastering this template unlocks LeetCode 2416, 2185, 1804, and a long tail of prefix-aggregation problems.