Sum of Scores of Built Strings — Problem & Solution
Sum of Scores of Built Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Sum of Scores of Built Strings is a hard coding problem on strings, binary search and rolling hash, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Binary Search, Rolling Hash, String Matching
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A string of length n is built one character at a time by prepending to the front. Label the intermediate strings s_1, s_2, …, s_n, where s_i has length i — so s_i is the suffix of the final string s = s_n made of its last i characters.
The score of s_i is the length of the longest common prefix of s_i and s_n.
Given the final string s, return the sum of the scores of all of s_1, …, s_n.
CodeKairo bound: s is at most 60,000 characters here, so the answer always fits in a 32-bit integer.
Example 1
Input: s = "kaikai"
Output: 9
Explanation: `kaikai` scores 6 and `kai` scores 3; every other suffix starts with a letter other than `k` and scores 0.
Example 2
Input: s = "aaaa"
Output: 10
Explanation: The suffixes score 1, 2, 3 and 4.
Example 3
Input: s = "abcab"
Output: 7
Explanation: `ab` scores 2 and `abcab` scores 5.
Constraints
1 <= s.length <= 6 * 10^4s consists of lowercase English letters
Hints for Sum of Scores of Built Strings
Hint 1
Each
s_iis a suffix ofs, so you need, for every suffix, the length of its longest common prefix withsitself.Hint 2
That array is exactly the Z-function of
s(withz[0] = n).Hint 3
Compute the Z-array in linear time with the
[l, r)window trick — reusez[i - l]inside the window and extend by direct comparison only pastr— then add it up.
How to solve Sum of Scores of Built Strings
The score of the suffix starting at index i is LCP(s[i..], s), which is the definition of z[i] in the Z-function. The answer is therefore the sum of the Z-array, computable in O(n).
Approach
- Set
z[0] = n(the whole string matches itself) and keep a window[l, r)— the rightmost segment known to equal a prefix ofs. - For each
ifrom 1: ifi < r, start fromz[i] = min(r - i, z[i - l]), becauses[l..r)mirrorss[0..r-l). - Extend
z[i]whiles[z[i]] == s[i + z[i]]. - If
i + z[i] > r, move the window to[i, i + z[i]). - Return the sum of all
z[i].
Why it works
Inside the window, the characters from i onward equal those from i - l, so z[i - l] is a valid lower bound as long as it stays inside the window — hence the min with r - i. Every successful extension pushes r to the right, and r never exceeds n, so the total number of character comparisons is linear.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Comparing each suffix with
sdirectly isO(n^2)— fine for a check, too slow for long strings. - Do not forget the full string itself: it contributes
n. - On the original problem (
nup to 10^5) the sum needs 64 bits; it fits here only because of the tighter bound.
Reference solution
Python
def sumScores(s: str) -> int:
n = len(s)
z = [0] * n
z[0] = n
l = r = 0
for i in range(1, n):
if i < r:
z[i] = min(r - i, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] > r:
l, r = i, i + z[i]
return sum(z)Java
public static int sumScores(String s) {
int n = s.length();
int[] z = new int[n];
z[0] = n;
int l = 0, r = 0;
long total = n;
for (int i = 1; i < n; i++) {
if (i < r) z[i] = Math.min(r - i, z[i - l]);
while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++;
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
total += z[i];
}
return (int) total;
}C++
int sumScores(string s) {
int n = s.size();
vector<int> z(n, 0);
z[0] = n;
int l = 0, r = 0;
long long total = n;
for (int i = 1; i < n; i++) {
if (i < r) z[i] = min(r - i, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
total += z[i];
}
return (int)total;
}JavaScript
var sumScores = function(s) {
var n = s.length;
var z = new Array(n).fill(0);
z[0] = n;
var l = 0, r = 0, total = n;
for (var i = 1; i < n; i++) {
if (i < r) z[i] = Math.min(r - i, z[i - l]);
while (i + z[i] < n && s.charCodeAt(z[i]) === s.charCodeAt(i + z[i])) z[i]++;
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
total += z[i];
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Binary Search