Problem

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 _thesum of the score of every _si.

Examples

Example 1

1
2
3
4
5
6
7
8
9

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

1
2
3
4
5
6
7
8

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 <= 10^5
  • s consists of lowercase English letters.

Solution

Approach

For each si, the score is the length of the longest common prefix between si and s. This is equivalent to computing the Z-array (Z-algorithm) for the string s. The sum of all Z-values plus n (for the full string) gives the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    long long sumScores(string s) {
        int n = s.size();
        vector<int> z(n);
        long long res = n;
        for (int i = 1, l = 0, r = 0; i < n; ++i) {
            if (i <= r) z[i] = min(r - i + 1, z[i - l]);
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
            if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
            res += z[i];
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public long sumScores(String s) {
        int n = s.length();
        int[] z = new int[n];
        long res = n;
        for (int i = 1, l = 0, r = 0; i < n; ++i) {
            if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]);
            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) ++z[i];
            if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
            res += z[i];
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun sumScores(s: String): Long {
        val n = s.length
        val z = IntArray(n)
        var res = n.toLong()
        var l = 0; var r = 0
        for (i in 1 until n) {
            if (i <= r) z[i] = minOf(r - i + 1, z[i - l])
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i]
            if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1 }
            res += z[i]
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def sumScores(self, s: str) -> int:
        n = len(s)
        z = [0] * n
        res = n
        l = r = 0
        for i in range(1, n):
            if i <= r:
                z[i] = min(r - i + 1, z[i - l])
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
            if i + z[i] - 1 > r:
                l, r = i, i + z[i] - 1
            res += z[i]
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn sum_scores(s: String) -> i64 {
        let n = s.len();
        let s = s.as_bytes();
        let mut z = vec![0; n];
        let mut res = n as i64;
        let (mut l, mut r) = (0, 0);
        for i in 1..n {
            if i <= r { z[i] = z[i-l].min(r-i+1); }
            while i + z[i] < n && s[z[i]] == s[i+z[i]] { z[i] += 1; }
            if i + z[i] - 1 > r { l = i; r = i + z[i] - 1; }
            res += z[i] as i64;
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

function sumScores(s: string): number {
    const n = s.length;
    const z = new Array(n).fill(0);
    let res = n;
    let l = 0, r = 0;
    for (let i = 1; i < n; ++i) {
        if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] === s[i + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
        res += z[i];
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)