Sum of Scores of Built Strings
Hard Z-algorithm
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
The string is built by adding characters to the front one at a time. Each intermediate string's score is the length of the longest common prefix it shares with the final string. Return the sum of all scores.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: for every suffix, how long a prefix of the full string does it start with? Add those up.
Why this works: that's exactly the Z-array, which the Z-algorithm builds in O(n) by reusing the furthest match window.
Example: "babab"
z = [5, 0, 3, 0, 1]sum = 9
✦Hints open one at a time
↗Approach
Compute the Z-array in O(n) using the [l, r] window of the rightmost match found so far. Sum z[1..n-1] plus n, using a long.
</>Solution (Java)
class Solution {
public long sumScores(String s) {
int n = s.length();
int[] z = new int[n];
long total = n; // the whole string scores n
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r) z[i] = Math.min(r - i, z[i - l]); // reuse the known window
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 total;
}
}!Common mistake
Using int for the sum — it can reach about n²/2 and overflow.
- Time: O(n).
- Space: O(n).