Skip to content

Latest commit

 

History

History
104 lines (80 loc) · 5.07 KB

README.md

File metadata and controls

104 lines (80 loc) · 5.07 KB

2223. Sum of Scores of Built Strings (Hard)

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.

Companies: Amazon

Related Topics:
String, Binary Search, Rolling Hash, Suffix Array, String Matching, Hash Function

Similar Questions:

Hints:

  • Each s_i is a suffix of the string s, so consider algorithms that can determine the longest prefix that is also a suffix.
  • Could you use the Z array from the Z algorithm to find the score of each s_i?

Solution 1. LPS (KMP)

Calculate lps (longest prefix and suffix) first.

Let cnt[i] be the number of times s[i] appears in matched prefixes. Initially cnt[i] are all 1s.

For s[i], we use its lps[i] to find s[j] (j = lps[i] - 1). If s[j] appears in cnt[j] prefixes, then s[i] can also show up in cnt[j] prefixes, plus the entire string which corresponds to the initial value 1.

For example:

s     =   b a b x b a b ...
index =   0 1 2 3 4 5 6 ...
lps   =   0 0 1 0 1 2 3 ...
cnt   =   1 1 2 1 2 2 3 ...

For the b at index 2, since its lps is 1, we look at s[0] and its cnt[0]=1. cnt[0]=1 means that the first b shows up in one prefix -- the entire string. Since s[0] shows up in one prefix starting from s[0], we know s[2] must also show up in at least one prefix starting from s[2]. s[2] also shows up in the entire string. So cnt[2] = cnt[0] + 1.

For the b at index 6, since its lps is 3, we look at s[2] and its cnt[2]=2. cnt[2]=2 means that s[2] shows up in two prefixes, s[0:] and s[2:]. And we know s[6] shows up in two prefixes, s[4:] and s[6:]. s[6] also shows up in the entire string. So cnt[6] = cnt[2] + 1

// OJ: https://leetcode.com/problems/sum-of-scores-of-built-strings
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    long long sumScores(string s) {
        long long N = s.size(), j = 0, ans = 0;
        vector<int> lps(N), cnt(N, 1);
        for (int i = 1; i < N; ++i) {
            while (j > 0 && s[i] != s[j]) j = lps[j - 1];
            j += s[i] == s[j];
            lps[i] = j;
        }
        for (int i = 0; i < N; ++i) {
            if (lps[i]) cnt[i] += cnt[lps[i] - 1];
        }
        return accumulate(begin(cnt), end(cnt), 0LL);
    }
};