Problem Description
Build a string s of length n one character at a time by prepending each new character. For each built string sᵢ (where s₁ is the string containing the last character of s, s₂ contains the last two characters, and so on until sₙ equals s), compute its score defined as the length of the longest common prefix between sᵢ and the final string s. Return the sum of scores for all sᵢ.
Key Insights
- The built string sᵢ corresponds to the suffix s[n-i:] of the final string s.
- The score for sᵢ is the longest common prefix between s[n-i:] and s.
- This is directly related to the Z algorithm, which computes an array z where z[i] is the length of the longest substring starting at index i that matches the prefix of s.
- For sₙ (i.e. when i = n), the score is n since sₙ equals s.
- The final answer is computed as the sum of z[0] (which we set to n) and all subsequent z-values.
Space and Time Complexity
Time Complexity: O(n) Space Complexity: O(n)
Solution
We solve the problem by computing the Z array for the final string s using the standard two-pointer technique. The Z array allows us to quickly obtain the longest prefix match between any substring of s (i.e., s[i:]) and s itself. Note that the built strings sᵢ are exactly the suffixes of s, so summing the Z values gives us the desired result. The only twist is that z[0] is not computed by the algorithm, but by definition its value should be n (the full length). Hence, we set z[0] = n and then sum all the z-values.