Skip to content

2223. Sum of Scores of Built Strings

SourceBiweekly Contest 75 Q4DifficultyHardRating2220

Description

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.

 

Example 1:

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:

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

Solutions

Solution 1

Thinking

Each \(s_i\) is the length-\(i\) suffix of \(s\), and its score is the LCP of that suffix with \(s\) itself. Comparing every suffix naively is \(O(n^2)\) and fails for \(n \le 10^5\).

Those LCPs are the Z-array: \(z[i]\) is the LCP of \(s[i:]\) with \(s\), and \(z[0]=n\). Summing the Z-array after a linear construction is enough. String hashing plus binary search on each start is an \(O(n \log n)\) alternative.

Compute the Z-array of \(s\), where \(z[i]\) is the LCP of \(s[i:]\) with \(s\). The score of the length-\(i\) suffix \(s_i\) is \(z[n-i]\), and the whole string scores \(n\). Summing the Z-array and adding \(n\) is the answer.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of \(s\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def sumScores(self, s: str) -> int:
        n = len(s)
        z = [0] * 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
        return n + sum(z)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public long sumScores(String s) {
        int n = s.length();
        int[] z = new int[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;
            }
        }
        long ans = n;
        for (int x : z) {
            ans += x;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    long long sumScores(string s) {
        int n = s.size();
        vector<int> z(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;
            }
        }
        return n + accumulate(z.begin(), z.end(), 0LL);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func sumScores(s string) int64 {
    n := len(s)
    z := make([]int, n)
    for i, l, r := 1, 0, 0; i < n; i++ {
        if i <= r {
            z[i] = min(r-i+1, z[i-l])
        }
        for i+z[i] < n && s[z[i]] == s[i+z[i]] {
            z[i]++
        }
        if i+z[i]-1 > r {
            l, r = i, i+z[i]-1
        }
    }
    ans := int64(n)
    for _, x := range z {
        ans += int64(x)
    }
    return ans
}

Comments