Sum of Prefix Scores of Strings
HardPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Define a
TrieNodeclass containing an array of children (e.g., size 26 for lowercase English letters) and an integercount. - First Pass (Build Trie):
- Create a
rootnode for the Trie. - Iterate through each
wordin thewordsarray. - For each
word, traverse the Trie from theroot, character by character. - For each character, move to the corresponding child node. If it doesn't exist, create it.
- Increment the
countof the visited node. Thiscountrepresents the score of the prefix ending at that node.
- Create a
- Second Pass (Calculate Scores):
- Initialize an integer array
answerof sizen. - Iterate through each
wordat indexiin thewordsarray. - Initialize
totalScoreto 0. - Traverse the Trie again for the current
word, character by character. - At each node in the traversal, add its
counttototalScore. - After traversing the entire word, store
totalScoreinanswer[i].
- Initialize an integer array
- Return the
answerarray.
Walkthrough
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:
- 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
countfield. By the end of this pass, thecountat any node will represent the score of the prefix corresponding to that node. - Calculate Sum of Scores: We iterate through the input
wordsarray again. For each word, we traverse the Trie following the path of its characters. As we visit each node along the path, we add itscountto 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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize an integer array
answerof the same size aswords. - Loop through each word
words[i]in the input array. - For each
words[i], initialize atotalScoreto 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
prefixScoreto 0. - Loop through all words
words[j]in the input array. - If
words[j]starts with the prefixp, incrementprefixScore.
- Initialize
- Add the calculated
prefixScoretototalScore. - After checking all prefixes of
words[i], storetotalScoreinanswer[i]. - Return the
answerarray.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Create a
HashMap<String, Integer>to store the score of each prefix. - First Pass (Populate Map):
- Iterate through each word
win thewordsarray. - For each word
w, generate all its non-empty prefixes. - For each prefix
p, increment its count in the hash map.
- Iterate through each word
- Second Pass (Calculate Answers):
- Initialize an integer array
answerof sizen. - Iterate through each word
words[i]. - Initialize
totalScoreto 0. - For each
words[i], generate all its non-empty prefixesp. - Look up the score of
pin the hash map and add it tototalScore. - Store
totalScoreinanswer[i].
- Initialize an integer array
- Return the
answerarray.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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 ; } }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 )); };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 ; } };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 ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.