Sum of Scores of Built Strings - Solution & Explanation
Problem Statement
You are building a string s of length n one character at a time, prepending each new character to the front of the string. The strings are labeled from 1 to n, where the string with length i is labeled si.
- For example, for
s = "abaca",s1 == "a",s2 == "ca",s3 == "aca", etc.
The score of si is the length of the longest common prefix between si and sn (Note that s == sn).
Given the final string s, return the sum of the score of every si.
Example 1:
Input: s = "babab" Output: 9 Explanation: For s1 == "b", the longest common prefix is "b" which has a score of 1. For s2 == "ab", there is no common prefix so the score is 0. For s3 == "bab", the longest common prefix is "bab" which has a score of 3. For s4 == "abab", there is no common prefix so the score is 0. For s5 == "babab", the longest common prefix is "babab" which has a score of 5. The sum of the scores is 1 + 0 + 3 + 0 + 5 = 9, so we return 9.
Example 2:
Input: s = "azbazbzaz" Output: 14 Explanation: For s2 == "az", the longest common prefix is "az" which has a score of 2. For s6 == "azbzaz", the longest common prefix is "azb" which has a score of 3. For s9 == "azbazbzaz", the longest common prefix is "azbazbzaz" which has a score of 9. For all other si, the score is 0. The sum of the scores is 2 + 3 + 9 = 14, so we return 14.
Constraints:
1 <= s.length <= 105sconsists of lowercase English letters.
Approach Overview
Problem Overview: You receive a string s. For every suffix starting at index i, compute the length of the longest common prefix between s and s[i:]. The score of the string is the sum of all these prefix matches. The task is to compute this total efficiently.
Approach 1: Naive Comparison Approach (Time: O(n^2), Space: O(1))
The straightforward method compares the original string with every suffix. For index i, start two pointers: one at 0 and another at i. Increment both pointers while characters match to measure the longest common prefix length. Add this length to the total score. This requires scanning potentially the rest of the string for every starting position, which leads to quadratic time in the worst case. The approach is simple and useful for understanding the definition of the score, but it becomes too slow when the string length approaches the problem constraints.
Approach 2: Optimized Z-Algorithm Approach (Time: O(n), Space: O(n))
The optimal solution uses the Z-algorithm, a classic technique from string matching. The Z-array stores the length of the longest substring starting at index i that matches the prefix of the string. This is exactly the value required for each suffix comparison in the problem.
The algorithm maintains a window [L, R] representing the rightmost segment where a prefix match has already been computed. For each index, reuse previously computed values if the index falls inside this window. Otherwise, expand the match manually by comparing characters. This reuse avoids redundant comparisons and ensures linear processing. The final score is simply the sum of all Z values plus n (since the full string matches itself).
This technique appears frequently in advanced string problems and competes with methods like rolling hash or suffix arrays. Z-algorithm is preferred here because it computes prefix matches for every position in a single pass without hashing or binary search.
Recommended for interviews: Interviewers expect the Z-algorithm solution. The brute force approach shows you understand the definition of the score and prefix comparisons. The optimized solution demonstrates knowledge of linear-time string matching techniques and the ability to avoid repeated comparisons, which is the real signal of algorithmic skill.
Approach 1: Naive Comparison Approach
In this approach, we iteratively calculate the longest common prefix for each substring si with the full string s. We start from each position i of the string and compare it with the beginning of the string, checking for matching prefixes. This approach takes a direct comparison route and is easy to understand but can be improved in terms of efficiency.
This C code implements the naive approach by iterating over all possible prefixes starting from each index and calculating their scores. It uses two loops: the outer loop tracks the starting position of the substring si, and the inner loop evaluates how many consecutive characters match the start of s.
Complexity
Time Complexity: O(n^2); Space Complexity: O(1)
Approach 2: Optimized Z-Algorithm Approach
Instead of recalculating the prefix scores repeatedly, we utilize the Z-algorithm, which is efficient for pattern matching problems. The Z-array for a string stores the length of the longest substring starting from position i that is also a prefix of the string. With this pre-computed array, we can quickly determine the score for each si without redundant comparisons.
This C code utilizes the Z-algorithm to efficiently calculate the score sum. The algorithm processes the string in linear time and pre-computes the Z-array where each Z[i] value contributes to the score of distinct prefixes.
Complexity
Time Complexity: O(n); Space Complexity: O(n)
Complexity Comparison
| Approach | Complexity |
|---|---|
| Naive Comparison Approach | Time Complexity: O(n^2); Space Complexity: O(1) |
| Optimized Z-Algorithm Approach | Time Complexity: O(n); Space Complexity: O(n) |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Comparison | O(n^2) | O(1) | Useful for understanding the definition of prefix scores or when input size is very small |
| Z-Algorithm | O(n) | O(n) | Best general solution; computes prefix matches for all suffixes efficiently |
Video Solution
2223. Sum of Scores of Built Strings || Leetcode BiWeekly Contest 75 || Leetcode 2223 • Bro Coders • 2,262 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Sum of Scores of Built Strings easy or hard?
Sum of Scores of Built Strings Python/Java solution
How to solve Sum of Scores of Built Strings in O(n)?
What is the best approach for Sum of Scores of Built Strings?
Is Sum of Scores of Built Strings asked at Google/Amazon/Meta?
What data structure is used in Sum of Scores of Built Strings?
What is the time complexity of Sum of Scores of Built Strings?
Ready to solve this problem?
Practice Sum of Scores of Built Strings with our built-in code editor and test cases.
Practice on FleetCode