Sum of scores of built strings

String Binary Search Rolling Hash Suffix Array String Matching Hash Function

46.7% acceptance

Feb 25, 2026

298

189

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn sum_scores(s: String) -> i64 {
    // si = s[n-i..], score = LCP(si, s) = Z[n-i] from Z-function
    // Sum of all scores = sum of Z array
    let s: Vec<u8> = s.bytes().collect();
    let n = s.len();
    let mut z = vec![0usize; n];
    z[0] = n;
    let mut l = 0usize;
    let mut r = 0usize;
    for i in 1..n {
      if i < r {
        z[i] = (r - i).min(z[i - l]);
      }
      while i + z[i] < n && s[z[i]] == s[i + z[i]] {
        z[i] += 1;
      }
      if i + z[i] > r {
        l = i;
        r = i + z[i];
      }
    }
    z.iter().map(|&x| x as i64).sum()
  }
}