Sum of Prefix Scores of Strings solution and explanation
Google
9 more videos on this problem
Sum of Prefix Scores of Strings - Leetcode 2416 - PythonNeetCodeIO · 19:44 · 9K views
Sum of Prefix Scores of Strings | Trie | Full Easy Dry Run | Leetcode 2416 | codestorywithMIKcodestorywithMIK · 31:21 · 9K views
2416. Sum of Prefix Scores of Strings | Leetcode Weekly 311 | LeetCode 2416Bro Coders · 15:31 · 1K views
Leetcode 2416 Sum of Prefix Scores of Strings | Coding Decoded SDE SheetCoding Decoded · 7:47 · 1K views
2416. Sum of Prefix Scores of Strings | tries | Leetcode Daily Challenge | DSA | JavaShashCode · 14:15 · 1K views
SUM OF PREFIX SCORES OF STRINGS | LEETCODE 2416 | PYTHON TRIE SOLUTIONCracking FAANG · 17:07 · 1K views
2416. Sum of Prefix Scores of Strings (Leetcode Hard)Programming Live with Larry · 10:44 · 398 views
2416. Sum of Prefix Scores of Strings || Leetcode Hard || Trie || CPPKomal Pal · 14:17 · 94 views
LeetCode 2416 - Sum of Prefix Scores of Strings - JavaAlpha-Code · 9:23 · 87 views
Leetcode September Challenge Day 25 2416. Sum of prefix Scores of Strings #leetcode #challenge #dsaADA Lovelace Coders · 5:47 · 54 views
The 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"is2, 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 <= 10001 <= words[i].length <= 1000words[i]consists of lowercase English letters.
Approach overview
Problem Overview: You are given an array of strings. For each word, compute the sum of scores of all its prefixes. The score of a prefix is the number of words in the array that start with that prefix. The result for each word is the total score of every prefix it contains.
Approach 1: Hashtable for Counting Prefix Frequency (Time: O(n * L^2), Space: O(n * L^2))
This approach explicitly counts how many times every prefix appears using a hash map. Iterate through each word and generate all prefixes (word[:1], word[:2], ...). Store them in a hash table with their frequency. In a second pass, recompute each word's score by summing the counts of its prefixes from the map. The idea is straightforward and easy to implement using string operations and counting, but prefix generation repeatedly creates substrings, which increases both runtime and memory usage for long words.
Approach 2: Prefix Trie Construction (Time: O(N), Space: O(N))
A Trie stores prefixes efficiently while sharing common paths between words. Insert every word into the Trie character by character and maintain a counter at each node representing how many words pass through that prefix. After building the Trie, compute the score of a word by traversing its characters again and summing the stored counters at each node. Because each character is processed a constant number of times, the total work is proportional to the total number of characters N. This avoids repeated substring creation and naturally aggregates prefix counts.
Recommended for interviews: The Trie approach is the expected solution. It demonstrates understanding of prefix-based data structures and reduces the complexity to O(N). Starting with the hash map prefix counting approach shows that you understand the scoring rule, but the Trie solution proves you can optimize prefix aggregation efficiently.
Approach 1: Prefix Trie Construction
A Trie is an efficient tree-like data structure that allows efficient retrieval of a string's prefix scores. We start by inserting each word into the Trie, along with maintaining a count at each node to track how many words share that prefix. Then, for each word, we traverse its prefixes in the Trie to compute the prefix score by collecting the counts stored at each relevant node.
class TrieNode:
def __init__(self):
self.children = {}
self.count = 0
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.count += 1
def calculate_prefix_score(self, word):
node = self.root
score = 0
for char in word:
node = node.children[char]
score += node.count
return score
def sum_of_prefix_scores(words):
trie = Trie()
for word in words:
trie.insert(word)
return [trie.calculate_prefix_score(word) for word in words]
words = ["abc", "ab", "bc", "b"]
print(sum_of_prefix_scores(words))import java.util.*;
class TrieNode {
TrieNode[] children = new TrieNode[26];
int count = 0;
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
if (node.children[ch - 'a'] == null) {
node.children[ch - 'a'] = new TrieNode();
}
node = node.children[ch - 'a'];
node.count++;
}
}
public int calculatePrefixScore(String word) {
TrieNode node = root;
int score = 0;
for (char ch : word.toCharArray()) {
node = node.children[ch - 'a'];
score += node.count;
}
return score;
}
}
public class Solution {
public int[] sumOfPrefixScores(String[] words) {
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
int[] result = new int[words.length];
for (int i = 0; i < words.length; i++) {
result[i] = trie.calculatePrefixScore(words[i]);
}
return result;
}
public static void main(String[] args) {
String[] words = {"abc", "ab", "bc", "b"};
int[] result = new Solution().sumOfPrefixScores(words);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct TrieNode {
TrieNode* children[26];
int count;
TrieNode() {
fill_n(children, 26, nullptr);
count = 0;
}
};
class Trie {
TrieNode* root;
public:
Trie() { root = new TrieNode(); }
void insert(const string& word) {
TrieNode* node = root;
for (char ch : word) {
if (!node->children[ch - 'a'])
node->children[ch - 'a'] = new TrieNode();
node = node->children[ch - 'a'];
node->count++;
}
}
int calculatePrefixScore(const string& word) {
TrieNode* node = root;
int score = 0;
for (char ch : word) {
node = node->children[ch - 'a'];
score += node->count;
}
return score;
}
};
vector<int> sumOfPrefixScores(vector<string>& words) {
Trie trie;
for (const string& word : words)
trie.insert(word);
vector<int> answer;
for (const string& word : words)
answer.push_back(trie.calculatePrefixScore(word));
return answer;
}
int main() {
vector<string> words = {"abc", "ab", "bc", "b"};
vector<int> answer = sumOfPrefixScores(words);
for (int ans : answer)
cout << ans << " ";
cout << endl;
return 0;
}class TrieNode {
constructor() {
this.children = {};
this.count = 0;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
node.count++;
}
}
calculatePrefixScore(word) {
let node = this.root;
let score = 0;
for (let char of word) {
node = node.children[char];
score += node.count;
}
return score;
}
}
function sumOfPrefixScores(words) {
const trie = new Trie();
for (let word of words) {
trie.insert(word);
}
return words.map(word => trie.calculatePrefixScore(word));
}
const words = ["abc", "ab", "bc", "b"];
console.log(sumOfPrefixScores(words));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ALPHABET_SIZE 26
struct TrieNode {
struct TrieNode* children[ALPHABET_SIZE];
int count; // Count of words sharing this prefix
};
struct TrieNode* getNode() {
struct TrieNode* pNode = (struct TrieNode*)malloc(sizeof(struct TrieNode));
pNode->count = 0;
for (int i = 0; i < ALPHABET_SIZE; i++)
pNode->children[i] = NULL;
return pNode;
}
void insert(struct TrieNode* root, const char* key) {
struct TrieNode* pCrawl = root;
while (*key) {
int index = *key - 'a';
if (!pCrawl->children[index])
pCrawl->children[index] = getNode();
pCrawl = pCrawl->children[index];
pCrawl->count++;
key++;
}
}
int calculatePrefixScore(struct TrieNode* root, const char* key) {
struct TrieNode* pCrawl = root;
int score = 0;
while (*key) {
int index = *key - 'a';
if (pCrawl->children[index]) {
pCrawl = pCrawl->children[index];
score += pCrawl->count;
}
key++;
}
return score;
}
void prefixScores(char* words[], int n, int* answer) {
struct TrieNode* root = getNode();
for (int i = 0; i < n; i++)
insert(root, words[i]);
for (int i = 0; i < n; i++)
answer[i] = calculatePrefixScore(root, words[i]);
}
int main() {
char* words[] = {"abc", "ab", "bc", "b"};
int n = sizeof(words) / sizeof(words[0]);
int answer[n];
prefixScores(words, n, answer);
for (int i = 0; i < n; i++)
printf("answer[%d] = %d\n", i, answer[i]);
return 0;
}using System;
using System.Collections.Generic;
class TrieNode {
public TrieNode[] Children = new TrieNode[26];
public int Count = 0;
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void Insert(string word) {
TrieNode node = root;
foreach (char ch in word) {
int index = ch - 'a';
if (node.Children[index] == null)
node.Children[index] = new TrieNode();
node = node.Children[index];
node.Count++;
}
}
public int CalculatePrefixScore(string word) {
TrieNode node = root;
int score = 0;
foreach (char ch in word) {
node = node.Children[ch - 'a'];
score += node.Count;
}
return score;
}
}
class Solution {
public int[] SumOfPrefixScores(string[] words) {
Trie trie = new Trie();
foreach (string word in words)
trie.Insert(word);
int[] result = new int[words.Length];
for (int i = 0; i < words.Length; i++)
result[i] = trie.CalculatePrefixScore(words[i]);
return result;
}
public static void Main() {
string[] words = {"abc", "ab", "bc", "b"};
int[] result = new Solution().SumOfPrefixScores(words);
Console.WriteLine(string.Join(" ", result));
}
}The Python solution initializes a Trie to hold the words, incrementing the count at each node during insertion. To determine prefix scores, we walk along the Trie and sum up the node counts collected along the way.
Time complexity is O(n * m), since each insertion and calculation takes linear time proportional to word length. Space complexity is O(N * m), considering Trie structure requirements for storing every character.
Approach 2: Hashtable for Counting Prefix Frequency
We can also use a hashtable (or dictionary) to count how often each prefix appears in the list of words. Iterate through each word and generate all its prefixes, updating their counts in the hashtable. Afterwards, compute the sum of counts for each full word by referencing its prefixes in the hashtable.
def sum_of_prefix_scores(words):
prefix_count = {}
for word in words:
prefix = ''
for char in word:
prefix += char
if prefix in prefix_count:
prefix_count[prefix] += 1
else:
prefix_count[prefix] = 1
result = []
for word in words:
prefix = ''
count = 0
for char in word:
prefix += char
count += prefix_count.get(prefix, 0)
result.append(count)
return result
words = ["abc", "ab", "bc", "b"]
print(sum_of_prefix_scores(words))import java.util.*;
public class Solution {
public int[] sumOfPrefixScores(String[] words) {
Map<String, Integer> prefixCount = new HashMap<>();
for (String word : words) {
String prefix = "";
for (char ch : word.toCharArray()) {
prefix += ch;
prefixCount.put(prefix, prefixCount.getOrDefault(prefix, 0) + 1);
}
}
int[] result = new int[words.length];
for (int i = 0; i < words.length; i++) {
String prefix = "";
int sum = 0;
for (char ch : words[i].toCharArray()) {
prefix += ch;
sum += prefixCount.get(prefix);
}
result[i] = sum;
}
return result;
}
public static void main(String[] args) {
String[] words = {"abc", "ab", "bc", "b"};
int[] result = new Solution().sumOfPrefixScores(words);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
using namespace std;
vector<int> sumOfPrefixScores(vector<string>& words) {
unordered_map<string, int> prefixCount;
for (const string& word : words) {
string prefix = "";
for (char ch : word) {
prefix += ch;
prefixCount[prefix]++;
}
}
vector<int> result;
for (const string& word : words) {
string prefix = "";
int count = 0;
for (char ch : word) {
prefix += ch;
count += prefixCount[prefix];
}
result.push_back(count);
}
return result;
}
int main() {
vector<string> words = {"abc", "ab", "bc", "b"};
vector<int> result = sumOfPrefixScores(words);
for (int res : result)
cout << res << " ";
cout << endl;
return 0;
}function sumOfPrefixScores(words) {
const prefixCount = {};
for (const word of words) {
let prefix = '';
for (const char of word) {
prefix += char;
if (prefixCount[prefix] == undefined) {
prefixCount[prefix] = 0;
}
prefixCount[prefix]++;
}
}
return words.map(word => {
let prefix = '';
let score = 0;
for (const char of word) {
prefix += char;
score += prefixCount[prefix];
}
return score;
});
}
const words = ["abc", "ab", "bc", "b"];
console.log(sumOfPrefixScores(words));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_WORD_LENGTH 1000
#define TABLE_SIZE 1000003
typedef struct Node {
char *key;
int value;
struct Node *next;
} Node;
unsigned long hash(const char *str) {
unsigned long hash = 5381;
int c;
while ((c = *str++))
hash = ((hash << 5) + hash) + c;
return hash;
}
void insert(Node **table, const char *key) {
unsigned long index = hash(key) % TABLE_SIZE;
Node *entry = table[index];
while (entry != NULL) {
if (strcmp(entry->key, key) == 0) {
entry->value += 1;
return;
}
entry = entry->next;
}
Node *new_node = malloc(sizeof(Node));
new_node->key = strdup(key);
new_node->value = 1;
new_node->next = table[index];
table[index] = new_node;
}
int get(Node **table, const char *key) {
unsigned long index = hash(key) % TABLE_SIZE;
Node *entry = table[index];
while (entry != NULL) {
if (strcmp(entry->key, key) == 0)
return entry->value;
entry = entry->next;
}
return 0;
}
void prefixScores(char *words[], int n, int *answer) {
Node *table[TABLE_SIZE] = {NULL};
char prefix[MAX_WORD_LENGTH];
for (int i = 0; i < n; i++) {
strcpy(prefix, "");
for (int j = 0; words[i][j] != '\0'; j++) {
prefix[j] = words[i][j];
prefix[j + 1] = '\0';
insert(table, prefix);
}
}
for (int i = 0; i < n; i++) {
strcpy(prefix, "");
answer[i] = 0;
for (int j = 0; words[i][j] != '\0'; j++) {
prefix[j] = words[i][j];
prefix[j + 1] = '\0';
answer[i] += get(table, prefix);
}
}
}
int main() {
char *words[] = {"abc", "ab", "bc", "b"};
int n = sizeof(words) / sizeof(words[0]);
int answer[n];
prefixScores(words, n, answer);
for (int i = 0; i < n; i++)
printf("answer[%d] = %d\n", i, answer[i]);
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public int[] SumOfPrefixScores(string[] words) {
Dictionary<string, int> prefixCount = new Dictionary<string, int>();
foreach (string word in words) {
string prefix = "";
foreach (char ch in word) {
prefix += ch;
if (!prefixCount.ContainsKey(prefix))
prefixCount[prefix] = 0;
prefixCount[prefix]++;
}
}
int[] result = new int[words.Length];
for (int i = 0; i < words.Length; i++) {
string prefix = "";
int sum = 0;
foreach (char ch in words[i]) {
prefix += ch;
sum += prefixCount[prefix];
}
result[i] = sum;
}
return result;
}
public static void Main() {
string[] words = {"abc", "ab", "bc", "b"};
int[] result = new Solution().SumOfPrefixScores(words);
Console.WriteLine(string.Join(" ", result));
}
}The Python approach makes use of a dictionary to maintain prefix counts. It iteratively processes each word to populate the dictionary, then sums the hit counts for each word's prefixes to determine respective scores.
Time complexity is O(n * m), as each word undergoes prefix handling. Space complexity aligns with O(N * m), based on prefix diversity managed in the dictionary.
Approach 3: Prefix Tree
We can use a prefix tree to maintain all prefixes of the strings and count the occurrences of each prefix.
Define the prefix tree node structure Trie, which includes two properties:
children: An array of length 26 used to store the current node's children.cnt: The occurrence count of the current node.
Define two methods for the prefix tree:
insert: Inserts a string, adding its prefixes into the prefix tree.search: Searches for a string and returns the occurrence count of its prefixes.
We traverse all strings, inserting each string into the prefix tree. Then we traverse all strings again, calling the search method for each string and summing up the occurrence counts of each prefix.
Time complexity is O(L), and space complexity is O(L), where L is the total length of all strings.
class Trie {
children: Array<any>;
cnt: number;
constructor() {
this.children = Array(26);
this.cnt = 0;
}
insert(w: string): void {
let node = this;
for (const c of w) {
const idx = c.charCodeAt(0) - 'a'.charCodeAt(0);
if (!node.children[idx]) {
node.children[idx] = new Trie();
}
node = node.children[idx];
node.cnt++;
}
}
search(w: string): number {
let node = this;
let ans = 0;
for (const c of w) {
const idx = c.charCodeAt(0) - 'a'.charCodeAt(0);
if (!node.children[idx]) {
return ans;
}
node = node.children[idx];
ans += node.cnt;
}
return ans;
}
}
function sumPrefixScores(words: string[]): number[] {
const trie = new Trie();
for (const w of words) {
trie.insert(w);
}
return words.map(w => trie.search(w));
}type Trie struct {
children [26]*Trie
cnt int
}
func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(w string) {
node := this
for _, c := range w {
c -= 'a'
if node.children[c] == nil {
node.children[c] = newTrie()
}
node = node.children[c]
node.cnt++
}
}
func (this *Trie) search(word string) int {
node := this
ans := 0
for _, c := range word {
c -= 'a'
if node.children[c] == nil {
return ans
}
node = node.children[c]
ans += node.cnt
}
return ans
}
func sumPrefixScores(words []string) []int {
trie := newTrie()
for _, w := range words {
trie.insert(w)
}
ans := make([]int, len(words))
for i, w := range words {
ans[i] = trie.search(w)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Trie Construction | Time complexity is O(n * m), since each insertion and calculation takes linear time proportional to word length. Space complexity is O(N * m), considering Trie structure requirements for storing every character. |
| Hashtable for Counting Prefix Frequency | Time complexity is O(n * m), as each word undergoes prefix handling. Space complexity aligns with O(N * m), based on prefix diversity managed in the dictionary. |
| Prefix Tree | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hashtable for Counting Prefix Frequency | O(n * L^2) | O(n * L^2) | Simple implementation when constraints are small or when avoiding custom data structures |
| Prefix Trie Construction | O(N) | O(N) | Best for large datasets with many shared prefixes; optimal interview solution |
Frequently asked questions
Is Sum of Prefix Scores of Strings easy or hard?
LeetCode classifies this problem as Hard because it requires recognizing that prefix aggregation can be optimized using a Trie. The naive prefix counting solution is straightforward, but achieving linear time requires understanding how to share prefix computations across words.
Sum of Prefix Scores of Strings Python/Java solution
Most implementations use a Trie class with a fixed array or map for child nodes and a counter field. Insert all words to populate prefix counts, then traverse again to compute scores. The same logic works in Python, Java, C++, C#, and JavaScript with O(N) time complexity.
How to solve Sum of Prefix Scores of Strings in O(n)?
Build a Trie where each node stores how many words share that prefix. Insert every word and increment the node count as you traverse characters. To compute the score of a word, traverse its characters again and accumulate the stored counts. Since every character is visited a constant number of times, the total runtime is linear in the number of characters.
What is the best approach for Sum of Prefix Scores of Strings?
The Trie-based prefix counting approach is the most efficient. Each character of every word is inserted once into the Trie while maintaining a counter at each node. A second traversal sums the counts for the prefixes of each word, giving overall O(N) time where N is the total number of characters.
Is Sum of Prefix Scores of Strings asked at Google/Amazon/Meta?
Prefix-based counting problems using Trie structures frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving prefix frequency, autocomplete, or dictionary matching are common system and algorithm interview questions.
What data structure is used in Sum of Prefix Scores of Strings?
The optimal solution uses a Trie (prefix tree). Each node represents a prefix and stores how many words share that prefix. Hash maps can also be used to count prefix frequencies, but they are less efficient because they require generating and storing every prefix string.
What is the time complexity of Sum of Prefix Scores of Strings?
The optimal Trie solution runs in O(N) time where N is the total number of characters across all words. Each character is processed during insertion and once more during prefix score calculation. The space complexity is also O(N) for storing Trie nodes.