{x}
blog image

Sum of Scores of Built Strings

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.

Solution Explanation and Code

This problem asks to calculate the sum of scores for all prefixes of a given string s. The score of a prefix s<sub>i</sub> is the length of the longest common prefix between s<sub>i</sub> and the full string s.

The most efficient approach involves calculating the longest common prefix (LCP) between the full string s and each of its prefixes. We can achieve this using a single iteration through the string.

Algorithm:

  1. Initialization: Initialize a variable total_score to 0 and a variable lcp_length to 0. lcp_length will track the length of the longest common prefix found so far.

  2. Iteration: Iterate through the string s from the end (last character) to the beginning (first character).

  3. LCP Calculation: For each character c at index i:

    • If c matches the character at index lcp_length in s, increment lcp_length. This indicates an extension of the common prefix.
    • Add lcp_length to total_score. This represents the score of the prefix ending at index i.

  4. Return: After iterating through the entire string, return total_score.

Time Complexity Analysis:

The algorithm iterates through the string s exactly once. Therefore, the time complexity is O(n), where n is the length of the string.

Space Complexity Analysis:

The algorithm uses only a few integer variables to store the total_score and lcp_length. The space complexity is therefore O(1), which is constant.

Code Implementation (Python):

def sumScores(s):
    """
    Calculates the sum of scores of all prefixes of a string.
 
    Args:
      s: The input string.
 
    Returns:
      The sum of the scores of all prefixes.
    """
    n = len(s)
    total_score = 0
    lcp_length = 0
    for i in range(n - 1, -1, -1):
        if s[i] == s[lcp_length]:
            lcp_length += 1
        else:
            lcp_length = 0  # Reset if mismatch
        total_score += lcp_length
    return total_score
 
# Example Usage
s = "babab"
result = sumScores(s)
print(f"Sum of scores for '{s}': {result}")  # Output: 9
 
s = "azbazbzaz"
result = sumScores(s)
print(f"Sum of scores for '{s}': {result}")  # Output: 14

Code Implementation (Java):

class Solution {
    public long sumScores(String s) {
        int n = s.length();
        long totalScore = 0;
        int lcpLength = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == s.charAt(lcpLength)) {
                lcpLength++;
            } else {
                lcpLength = 0;
            }
            totalScore += lcpLength;
        }
        return totalScore;
    }
}

Code Implementation (C++):

#include <string>
 
class Solution {
public:
    long long sumScores(string s) {
        long long totalScore = 0;
        int lcpLength = 0;
        for (int i = s.length() - 1; i >= 0; --i) {
            if (s[i] == s[lcpLength]) {
                lcpLength++;
            } else {
                lcpLength = 0;
            }
            totalScore += lcpLength;
        }
        return totalScore;
    }
};

Code Implementation (Go):

func sumScores(s string) int64 {
	n := len(s)
	totalScore := int64(0)
	lcpLength := 0
	for i := n - 1; i >= 0; i-- {
		if s[i] == s[lcpLength] {
			lcpLength++
		} else {
			lcpLength = 0
		}
		totalScore += int64(lcpLength)
	}
	return totalScore
}

All the above code implementations follow the same algorithm and have the same time and space complexity. They differ only in syntax according to their respective programming languages.