Sum of Prefix Scores of Strings

Sum of Prefix Scores of Strings

What is this problem about?

You are given an array of strings. The "score" of a single string is defined as the sum of the number of strings in the array that start with each of its prefixes. For example, if the string is "abc", its prefixes are "a", "ab", and "abc". If there are 5 strings starting with "a", 3 starting with "ab", and 2 starting with "abc", the score for "abc" is 5 + 3 + 2 = 10. You need to return the total scores for all strings in the input.

Why is this asked in interviews?

Companies like Google, Amazon, and Bloomberg ask this Hard-level problem to test proficiency with Trie (Prefix Tree) data structures. It's a perfect application for Tries because Tries naturally group strings by their shared prefixes. A brute-force approach (comparing every string's prefixes against all other strings) would be O(N² * L²), which is incredibly slow. A Trie reduces this to O(N * L).

Algorithmic pattern used

The pattern is "Trie with Prefix Counting."

1. Insert: Insert every string into a Trie. At each node (representing a prefix), maintain a count variable that increments every time a string passes through it.
2. Query: For each string, traverse the Trie along its characters. For each character you visit, add the count stored at that node to the string's total score.

Example explanation

Strings: ["abc", "ab"].

1. Insert "abc":
   • Node 'a': count=1
   • Node 'b': count=1
   • Node 'c': count=1
2. Insert "ab":
   • Node 'a': count=2
   • Node 'b': count=2 Query "abc":

• Prefix "a": count=2
• Prefix "ab": count=2
• Prefix "abc": count=1 Total Score = 2 + 2 + 1 = 5.

Common mistakes candidates make

1. Brute Force: Trying to use nested loops and string comparisons.
2. Memory Management: Creating a massive Trie without being mindful of memory. (Using an array of size 26 for children is usually acceptable).
3. Prefix Redundancy: Counting the same prefix multiple times for the same string (the Trie logic naturally avoids this).

Interview preparation tip

Tries are the "go-to" data structure for prefix-related problems. If you see "strings" and "prefixes" in a Hard problem, start by sketching out a Trie solution. Practice implementing a basic Trie from scratch, as many languages don't have one in their standard library.