Sum of Prefix Scores of Strings — Hard Problem & Solution

Problem statement

You are given an array words of n non-empty strings. The score of a string p is the number of strings in words that have p as a prefix (a string is a prefix of itself).

For each words[i], add up the scores of every non-empty prefix of words[i]. Return the array answer of length n where answer[i] is that sum.

Example 1

Input: words = ["code","coder","cod","kairo"]
Output: [11,12,9,5]
Explanation: For `code`: `c`, `co` and `cod` each prefix three words and `code` prefixes two, so 3 + 3 + 3 + 2 = 11.

Example 2

Input: words = ["aa","a","aa"]
Output: [5,3,5]
Explanation: Equal words are counted separately.

Example 3

Input: words = ["xyz"]
Output: [3]

Constraints

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

How to solve Sum of Prefix Scores of Strings

In a trie, each node is one distinct prefix. Counting how many inserted words pass through a node gives that prefix's score directly, so each answer is the sum of the counters along the word's own path.

Approach

1. Build a trie; give every node a counter pass.
2. Insert each word: walk/create its path from the root, incrementing pass on every node after the root.
3. For each word, walk its path again and sum the pass values — that is the answer for the word.

Why it works

A word w has p as a prefix exactly when w's path goes through p's node, so after all insertions pass[p] equals the score of p. The prefixes of words[i] are exactly the nodes on its path, so the sum along that path is the requested total.

Complexity

• Time — O(total length of all words)
• Space — O(26 · total length) for the trie

Pitfalls

• Comparing every prefix with every word is O(n^2 · L) — up to 10^9 character checks.
• Duplicate words must each be counted; do not deduplicate before inserting.
• A per-node array of 26 children is simplest; store the trie in flat arrays to keep allocation cheap.

Reference solution

Python

from typing import List

def sumPrefixScores(words: List[str]) -> List[int]:
    nxt = [[0] * 26]
    cnt = [0]
    for w in words:
        node = 0
        for ch in w:
            c = ord(ch) - 97
            if nxt[node][c] == 0:
                nxt[node][c] = len(nxt)
                nxt.append([0] * 26)
                cnt.append(0)
            node = nxt[node][c]
            cnt[node] += 1
    res = []
    for w in words:
        node = 0
        total = 0
        for ch in w:
            node = nxt[node][ord(ch) - 97]
            total += cnt[node]
        res.append(total)
    return res

JavaScript

var sumPrefixScores = function(words) {
    var total = 1;
    for (var i = 0; i < words.length; i++) total += words[i].length;
    var child = new Int32Array(total * 26);
    var cnt = new Int32Array(total);
    var nodes = 1;
    for (var i2 = 0; i2 < words.length; i2++) {
        var w = words[i2], node = 0;
        for (var j = 0; j < w.length; j++) {
            var c = w.charCodeAt(j) - 97;
            if (child[node * 26 + c] === 0) child[node * 26 + c] = nodes++;
            node = child[node * 26 + c];
            cnt[node]++;
        }
    }
    var res = [];
    for (var i3 = 0; i3 < words.length; i3++) {
        var w2 = words[i3], node2 = 0, sum = 0;
        for (var k = 0; k < w2.length; k++) {
            node2 = child[node2 * 26 + w2.charCodeAt(k) - 97];
            sum += cnt[node2];
        }
        res.push(sum);
    }
    return res;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Remove Boxes Hard
• Number of Squareful Arrays Hard
• Closest Subsequence Sum Hard
• Maximum Number of Achievable Transfer Requests Hard
• 24 Game Hard
• Verbal Arithmetic Puzzle Hard