Sum of Prefix Scores of Strings - Practice Coding Problems

Sum of Prefix Scores of Strings - 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.

Input & Output

Example 1 — Basic Case

$ Input: words = ["abc", "ab", "bc", "b"]

› Output: [5, 4, 3, 2]

💡 Note: For "abc": "a" appears in 2 words ("abc", "ab") = 2, "ab" appears in 2 words = 2, "abc" appears in 1 word = 1. Total: 2+2+1=5

Example 2 — Single Characters

$ Input: words = ["a"]

› Output: [1]

💡 Note: Only one word "a", so prefix "a" appears in 1 word, total score = 1

Example 3 — No Common Prefixes

$ Input: words = ["abc", "def", "ghi"]

› Output: [3, 3, 3]

💡 Note: No words share prefixes, so each word's prefixes appear only in itself, giving scores 1+1+1=3 for each

Constraints

1 ≤ words.length ≤ 1000
1 ≤ words[i].length ≤ 1000
words[i] consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words: ["abc", "ab", "bc", "b"]

Calculate

For each word, find score of each prefix

Output

Sum of prefix scores: [5, 4, 3, 2]

Key Takeaway

🎯 Key Insight: Use a trie to efficiently count how many words share each prefix

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is to use a trie data structure to efficiently count prefix occurrences. Best approach is the trie solution with Time: O(n × m), Space: O(n × m) where n is number of words and m is average word length.

Common Approaches

Approach	Time	Space	Notes
✓ Trie Data Structure	O(n × m)	O(n × m)	Build a trie and count prefix occurrences efficiently
Brute Force	O(n² × m²)	O(1)	For each word, check every prefix against all words

Trie Data Structure — Algorithm Steps

Build a trie from all words
Store count at each node (how many words pass through)
For each word, traverse trie and sum counts along the path

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Trie

Insert all words, count at each node

Store Counts

Each node knows how many words pass through

Sum Path

For each word, sum counts along its path

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TrieNode {
    struct TrieNode* children[26];
    int count;
} TrieNode;

TrieNode* createNode() {
    TrieNode* node = (TrieNode*)calloc(1, sizeof(TrieNode));
    return node;
}

int* solution(char** words, int wordsSize, int* returnSize) {
    *returnSize = wordsSize;
    
    // Build trie
    TrieNode* root = createNode();
    
    for (int i = 0; i < wordsSize; i++) {
        TrieNode* node = root;
        for (int j = 0; words[i][j]; j++) {
            int index = words[i][j] - 'a';
            if (!node->children[index]) {
                node->children[index] = createNode();
            }
            node = node->children[index];
            node->count++;
        }
    }
    
    // Calculate answers
    int* answer = (int*)malloc(wordsSize * sizeof(int));
    for (int i = 0; i < wordsSize; i++) {
        int totalScore = 0;
        TrieNode* node = root;
        
        for (int j = 0; words[i][j]; j++) {
            int index = words[i][j] - 'a';
            node = node->children[index];
            totalScore += node->count;
        }
        
        answer[i] = totalScore;
    }
    
    return answer;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for array of strings
    char** words = (char**)malloc(1000 * sizeof(char*));
    int wordsSize = 0;
    char* token = strtok(line + 1, ",");
    
    while (token != NULL) {
        // Remove quotes and whitespace
        while (*token == ' ' || *token == '"') token++;
        char* end = token + strlen(token) - 1;
        while (*end == ' ' || *end == '"' || *end == ']' || *end == '\n') {
            *end = '\0';
            end--;
        }
        
        words[wordsSize] = (char*)malloc(strlen(token) + 1);
        strcpy(words[wordsSize], token);
        wordsSize++;
        
        token = strtok(NULL, ",");
    }
    
    int returnSize;
    int* result = solution(words, wordsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

Build trie takes O(n × m) where n is number of words and m is average length, then O(n × m) to compute answers

✓ Linear Growth

Space Complexity

O(n × m)

Trie can store up to n × m nodes in worst case

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Trie Data Structure — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler