Watch 7 video solutions for Sum of Scores of Built Strings, a hard level problem involving String, Binary Search, Rolling Hash. This walkthrough by Bro Coders has 2,216 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 <= 105s consists of lowercase English letters.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 | 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 |