Sum of Scores of Built Strings

Hard
1257.

Sum of Scores of Built Strings

Sum of Scores of Built Strings is a hard coding problem on strings, binary search and rolling hash, asked in Amazon and Google interviews.

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^4
  • s consists of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var sumScores = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^4
  • s consists of lowercase English letters

Hints for Sum of Scores of Built Strings

  1. Hint 1

    Each s_i is a suffix of s, so you need, for every suffix, the length of its longest common prefix with s itself.

  2. Hint 2

    That array is exactly the Z-function of s (with z[0] = n).

  3. Hint 3

    Compute the Z-array in linear time with the [l, r) window trick — reuse z[i - l] inside the window and extend by direct comparison only past r — 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

  1. Set z[0] = n (the whole string matches itself) and keep a window [l, r) — the rightmost segment known to equal a prefix of s.
  2. For each i from 1: if i < r, start from z[i] = min(r - i, z[i - l]), because s[l..r) mirrors s[0..r-l).
  3. Extend z[i] while s[z[i]] == s[i + z[i]].
  4. If i + z[i] > r, move the window to [i, i + z[i]).
  5. 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 s directly is O(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 (n up 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