Sum of Prefix Scores of Strings

Hard
1260.

Sum of Prefix Scores of Strings

Sum of Prefix Scores of Strings is a hard coding problem on arrays, strings and counting, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @return {number[]}
 */
var sumPrefixScores = function(words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sum of Prefix Scores of Strings — Problem & Solution

Sum of Prefix Scores of Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Sum of Prefix Scores of Strings is a hard coding problem on arrays, strings and counting, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Strings, Counting, Trie
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Sum of Prefix Scores of Strings

  1. Hint 1

    The score of a prefix is "how many words pass through this prefix" — a trie stores exactly that if each node keeps a counter.

  2. Hint 2

    Insert every word, incrementing the counter of each node on its path.

  3. Hint 3

    Then walk each word's path again and add up the counters it visits.

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

Java

public static int[] sumPrefixScores(String[] words) {
    int total = 1;
    for (String w : words) total += w.length();
    int[] child = new int[total * 26];
    int[] cnt = new int[total];
    int nodes = 1;
    for (String w : words) {
        int node = 0;
        for (int j = 0; j < w.length(); j++) {
            int c = w.charAt(j) - 'a';
            if (child[node * 26 + c] == 0) child[node * 26 + c] = nodes++;
            node = child[node * 26 + c];
            cnt[node]++;
        }
    }
    int[] res = new int[words.length];
    for (int i = 0; i < words.length; i++) {
        int node = 0, sum = 0;
        for (int j = 0; j < words[i].length(); j++) {
            node = child[node * 26 + words[i].charAt(j) - 'a'];
            sum += cnt[node];
        }
        res[i] = sum;
    }
    return res;
}

C++

vector<int> sumPrefixScores(vector<string>& words) {
    int total = 1;
    for (const string& w : words) total += w.size();
    vector<int> child(total * 26, 0), cnt(total, 0);
    int nodes = 1;
    for (const string& w : words) {
        int node = 0;
        for (char ch : w) {
            int c = ch - 'a';
            if (child[node * 26 + c] == 0) child[node * 26 + c] = nodes++;
            node = child[node * 26 + c];
            cnt[node]++;
        }
    }
    vector<int> res;
    for (const string& w : words) {
        int node = 0, sum = 0;
        for (char ch : w) {
            node = child[node * 26 + (ch - 'a')];
            sum += cnt[node];
        }
        res.push_back(sum);
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings