# Sum of Prefix Scores of Strings
**Difficulty:** HARD
[External](https://leetcode.com/problems/sum-of-prefix-scores-of-strings)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-prefix-scores-of-strings
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, String, Trie
---
## Problem
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]`.

* For example, if `words = ["a", "ab", "abc", "cab"]`, then the score of `"ab"` is `2`, since `"ab"` is a prefix of both `"ab"` and `"abc"`.

Return _an array_ `answer` _of size_ `n` _where_ `answer[i]` _is the **sum** of scores of every **non-empty** prefix of_ `words[i]`.

**Note** that a string is considered as a prefix of itself.

**Example 1:**

**Input:** words = ["abc","ab","bc","b"]
**Output:** [5,4,3,2]
**Explanation:** The answer for each string is the following:
- "abc" has 3 prefixes: "a", "ab", and "abc".
- There are 2 strings with the prefix "a", 2 strings with the prefix "ab", and 1 string with the prefix "abc".
The total is answer[0] = 2 + 2 + 1 = 5.
- "ab" has 2 prefixes: "a" and "ab".
- There are 2 strings with the prefix "a", and 2 strings with the prefix "ab".
The total is answer[1] = 2 + 2 = 4.
- "bc" has 2 prefixes: "b" and "bc".
- There are 2 strings with the prefix "b", and 1 string with the prefix "bc".
The total is answer[2] = 2 + 1 = 3.
- "b" has 1 prefix: "b".
- There are 2 strings with the prefix "b".
The total is answer[3] = 2.

**Example 2:**

**Input:** words = ["abcd"]
**Output:** [4]
**Explanation:**
"abcd" has 4 prefixes: "a", "ab", "abc", and "abcd".
Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.

**Constraints:**

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

# Approaches
## Brute Force Iteration
A straightforward approach that directly implements the logic described in the problem. It involves multiple nested loops to generate every prefix for each word and then, for each prefix, iterate through the entire list of words to calculate its score.
**Time:** O(N^2 * M^2), where `N` is the number of words and `M` is the maximum length of a word. For each of the `N` words, we iterate through its `M` prefixes. For each prefix, we iterate through `N` words and perform a `startsWith` check which takes up to `O(M)`. This results in a very high time complexity. · **Space:** O(N + M), where N is the number of words and M is the maximum length of a word. O(N) for the answer array and O(M) to store the temporary prefix string.
**Pros:** Simple to understand and implement directly from the problem statement.
**Cons:** Highly inefficient and will not pass the time limits for the given constraints.
### Explanation
This method follows the problem definition literally. For each word in the input array, we first generate all of its non-empty prefixes. For instance, for the word "abc", the prefixes are "a", "ab", and "abc". Then, for each of these prefixes, we iterate through the entire `words` array again to count how many words start with that prefix. This count is the prefix's score. We sum up the scores for all prefixes of the original word to get its final total score. This process is repeated for every word in the input array.

```java
class Solution {
    public int[] sumPrefixScores(String[] words) {
        int n = words.length;
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            String currentWord = words[i];
            int totalScore = 0;
            for (int k = 1; k <= currentWord.length(); k++) {
                String prefix = currentWord.substring(0, k);
                int prefixScore = 0;
                for (int j = 0; j < n; j++) {
                    if (words[j].startsWith(prefix)) {
                        prefixScore++;
                    }
                }
                totalScore += prefixScore;
            }
            answer[i] = totalScore;
        }
        return answer;
    }
}
```
### Algorithm
- Initialize an integer array `answer` of the same size as `words`.
- Loop through each word `words[i]` in the input array.
- For each `words[i]`, initialize a `totalScore` to 0.
- Generate all non-empty prefixes of `words[i]`. This can be done by taking substrings from the beginning of the word with increasing length.
- For each prefix `p`, calculate its score:
    - Initialize `prefixScore` to 0.
    - Loop through all words `words[j]` in the input array.
    - If `words[j]` starts with the prefix `p`, increment `prefixScore`.
- Add the calculated `prefixScore` to `totalScore`.
- After checking all prefixes of `words[i]`, store `totalScore` in `answer[i]`.
- Return the `answer` array.

## Using a Hash Map to Cache Prefix Scores
This approach improves upon the brute-force method by avoiding redundant calculations. We first iterate through all words to compute the score for every possible prefix and store these scores in a hash map. Then, for each word, we sum the scores of its prefixes by looking them up in the map.
**Time:** O(L_sq), where `L_sq` is the sum of the squares of the lengths of all words (`sum(|w|^2)`). In the worst case, this is `O(N * M^2)` where `N` is the number of words and `M` is the maximum length. This is because for each word of length `k`, we generate `k` prefixes, and creating and hashing each prefix takes time proportional to its length. The sum of `1+2+...+k` is `O(k^2)`. This is likely too slow for the given constraints. · **Space:** O(L_sq), where `L_sq` is the sum of the squares of the lengths of all words (`sum(|w|^2)`). The space required for the hash map can be large, as it needs to store all unique prefixes. The total length of all unique prefixes can be up to `O(sum(|w|^2))`, which can be very large.
**Pros:** Faster than the pure brute-force approach by avoiding re-computation of scores.
**Cons:** Still inefficient in both time and space for the given constraints.; The overhead of string creation and hashing for every prefix is significant.
### Explanation
To optimize the brute-force approach, we can avoid re-calculating the score of the same prefix multiple times. We can use a hash map to store the scores of all prefixes encountered. 

The process involves two main passes. In the first pass, we iterate through every word, generate all its prefixes, and for each prefix, we update its count in the hash map. After this pass, the map contains every unique prefix and its corresponding score (i.e., how many words in the input start with it).

In the second pass, we iterate through the `words` array again. For each word, we generate its prefixes one by one, look up their pre-calculated scores in the hash map, and sum them up to get the final answer for that word.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] sumPrefixScores(String[] words) {
        Map<String, Integer> prefixCounts = new HashMap<>();
        for (String word : words) {
            for (int i = 1; i <= word.length(); i++) {
                String prefix = word.substring(0, i);
                prefixCounts.put(prefix, prefixCounts.getOrDefault(prefix, 0) + 1);
            }
        }

        int n = words.length;
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            String word = words[i];
            int totalScore = 0;
            for (int j = 1; j <= word.length(); j++) {
                String prefix = word.substring(0, j);
                totalScore += prefixCounts.get(prefix);
            }
            answer[i] = totalScore;
        }
        return answer;
    }
}
```
### Algorithm
- Create a `HashMap<String, Integer>` to store the score of each prefix.
- **First Pass (Populate Map):**
    - Iterate through each word `w` in the `words` array.
    - For each word `w`, generate all its non-empty prefixes.
    - For each prefix `p`, increment its count in the hash map.
- **Second Pass (Calculate Answers):**
    - Initialize an integer array `answer` of size `n`.
    - Iterate through each word `words[i]`.
    - Initialize `totalScore` to 0.
    - For each `words[i]`, generate all its non-empty prefixes `p`.
    - Look up the score of `p` in the hash map and add it to `totalScore`.
    - Store `totalScore` in `answer[i]`.
- Return the `answer` array.

## Optimal Approach using a Trie (Prefix Tree)
The most efficient solution utilizes a Trie data structure, which is perfectly suited for problems involving prefixes. We first build a Trie from all the words, incrementing a counter in each node to track how many words pass through it (i.e., the prefix score). Then, for each word, we traverse the Trie and sum the counters of the nodes corresponding to its prefixes.
**Time:** O(L), where `L` is the total number of characters in all words combined (`sum(|w|)`). We traverse each character of each word twice: once to build the Trie and once to calculate the scores. Each character operation (node creation, traversal, increment) takes constant time. · **Space:** O(L), where `L` is the total number of characters in all words combined (`sum(|w|)`). The space is dominated by the Trie. In the worst case, where there are no overlapping prefixes, the number of nodes in the Trie is equal to the total number of characters `L`. Each node has a constant size.
**Pros:** Highly efficient in both time and space.; It's the optimal solution for this problem as it avoids string manipulations and redundant computations.
**Cons:** Requires knowledge of the Trie data structure, making it slightly more complex to implement than the other approaches.
### Explanation
A Trie, or prefix tree, is an ideal data structure for this problem. Each node in the Trie can represent a character, and a path from the root to a node represents a prefix. We can augment the Trie node to store a count of how many words in the input array share the prefix represented by that node.

The algorithm works in two passes:
1.  **Build Trie and Count Prefixes:** We insert every word from the input array into the Trie. While inserting a word, we traverse the Trie character by character. For each node we visit (or create), we increment its `count` field. By the end of this pass, the `count` at any node will represent the score of the prefix corresponding to that node.
2.  **Calculate Sum of Scores:** We iterate through the input `words` array again. For each word, we traverse the Trie following the path of its characters. As we visit each node along the path, we add its `count` to a running total for the current word. This sum is the answer for that word.

This approach is highly efficient because it processes each character of each word a constant number of times.

```java
class TrieNode {
    TrieNode[] children;
    int count;

    public TrieNode() {
        children = new TrieNode[26];
        count = 0;
    }
}

class Solution {
    public int[] sumPrefixScores(String[] words) {
        TrieNode root = new TrieNode();

        // Pass 1: Build the Trie and count prefixes
        for (String word : words) {
            TrieNode curr = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (curr.children[index] == null) {
                    curr.children[index] = new TrieNode();
                }
                curr = curr.children[index];
                curr.count++;
            }
        }

        int n = words.length;
        int[] answer = new int[n];

        // Pass 2: Calculate the sum of scores for each word
        for (int i = 0; i < n; i++) {
            String word = words[i];
            TrieNode curr = root;
            int totalScore = 0;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                curr = curr.children[index];
                totalScore += curr.count;
            }
            answer[i] = totalScore;
        }

        return answer;
    }
}
```
### Algorithm
- Define a `TrieNode` class containing an array of children (e.g., size 26 for lowercase English letters) and an integer `count`.
- **First Pass (Build Trie):**
    - Create a `root` node for the Trie.
    - Iterate through each `word` in the `words` array.
    - For each `word`, traverse the Trie from the `root`, character by character.
    - For each character, move to the corresponding child node. If it doesn't exist, create it.
    - Increment the `count` of the visited node. This `count` represents the score of the prefix ending at that node.
- **Second Pass (Calculate Scores):**
    - Initialize an integer array `answer` of size `n`.
    - Iterate through each `word` at index `i` in the `words` array.
    - Initialize `totalScore` to 0.
    - Traverse the Trie again for the current `word`, character by character.
    - At each node in the traversal, add its `count` to `totalScore`.
    - After traversing the entire word, store `totalScore` in `answer[i]`.
- Return the `answer` array.

# Solutions
### Java

```java
class Trie { private Trie [] children = new Trie [ 26 ]; private int cnt ; public void insert ( String w ) { Trie node = this ; for ( char c : w . toCharArray ()) { c -= 'a' ; if ( node . children [ c ] == null ) { node . children [ c ] = new Trie (); } node = node . children [ c ]; ++ node . cnt ; } } public int search ( String w ) { Trie node = this ; int ans = 0 ; for ( char c : w . toCharArray ()) { c -= 'a' ; if ( node . children [ c ] == null ) { return ans ; } node = node . children [ c ]; ans += node . cnt ; } return ans ; } } class Solution { public int [] sumPrefixScores ( String [] words ) { Trie trie = new Trie (); for ( String w : words ) { trie . insert ( w ); } int [] ans = new int [ words . length ]; for ( int i = 0 ; i < words . length ; ++ i ) { ans [ i ] = trie . search ( words [ i ]); } return ans ; } }
```

### JavaScript

```javascript
class Trie { constructor () { this . children = {}; this . cnt = 0 ; } insert ( w ) { let node = this ; for ( const c of w ) { if ( ! node . children [ c ]) { node . children [ c ] = new Trie (); } node = node . children [ c ]; node . cnt ++ ; } } search ( w ) { let node = this ; let ans = 0 ; for ( const c of w ) { if ( ! node . children [ c ]) { return ans ; } node = node . children [ c ]; ans += node . cnt ; } return ans ; } } /** * @param {string[]} words * @return {number[]} */ var sumPrefixScores = function ( words ) { const trie = new Trie (); for ( const w of words ) { trie . insert ( w ); } return words . map ( w => trie . search ( w )); };
```

### CPP

```cpp
class Trie { private: vector < Trie *> children ; int cnt ; public: Trie () : children ( 26 ) , cnt ( 0 ) {} void insert ( string & w ) { Trie * node = this ; for ( char c : w ) { int idx = c - 'a' ; if ( ! node -> children [ idx ]) node -> children [ idx ] = new Trie (); node = node -> children [ idx ]; ++ node -> cnt ; } } int search ( string & w ) { Trie * node = this ; int ans = 0 ; for ( char c : w ) { int idx = c - 'a' ; if ( ! node -> children [ idx ]) return ans ; node = node -> children [ idx ]; ans += node -> cnt ; } return ans ; } }; class Solution { public: vector < int > sumPrefixScores ( vector < string >& words ) { Trie * trie = new Trie (); for ( auto & w : words ) { trie -> insert ( w ); } vector < int > ans ; for ( auto & w : words ) { ans . push_back ( trie -> search ( w )); } return ans ; } };
```

### Python

```python
class Trie : def __init__ ( self ): self . children = [ None ] * 26 self . cnt = 0 def insert ( self , w ): node = self for c in w : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] node . cnt += 1 def search ( self , w ): node = self ans = 0 for c in w : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : return ans node = node . children [ idx ] ans += node . cnt return ans class Solution : def sumPrefixScores ( self , words : List [ str ]) -> List [ int ]: trie = Trie () for w in words : trie . insert ( w ) return [ trie . search ( w ) for w in words ]
```