Sum of Scores of Built Strings

Problem 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. The score of si is the length of the longest common prefix between si and sn. Given the final string s, return the sum of the score of every si.

Key Insights

• The score of each substring si is determined by its longest common prefix with the final string sn.
• A naive approach would involve direct comparison for each substring, leading to a potentially inefficient solution.
• Efficiently calculating the longest common prefixes can leverage string matching techniques, potentially using algorithms like KMP (Knuth-Morris-Pratt) for preprocessing.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can utilize a single pass through the string while maintaining a variable to track the current longest common prefix. For each character in the string, we compare it to the corresponding character in the final string sn. If the characters match, we increase the length of the prefix; if they don't match, we reset the length. We accumulate these lengths to get the total score.

Code Solutions