Sum of Scores of Built Strings solution and explanation
6 more videos on this problem
2223. Sum of Scores of Built Strings || Leetcode BiWeekly Contest 75 || Leetcode 2223Bro Coders · 10:00 · 2K views
Leetcode BiWeekly 75 | 6036. Sum of Scores of Built StringscodingMohan · 17:10 · 899 views
【每日一题】LeetCode 2223. Sum of Scores of Built StringsHuifeng Guan · 33:42 · 668 views
Sum of Scores of Built String - Leetcode 2223 (Hard Problem) | Z Algorithm | String Matching ProblemBharat Khanna · 14:22 · 642 views
2223. Sum of Scores of Built Strings (Leetcode Hard)Programming Live with Larry · 3:37:46 · 495 views
Sum of Scores of Built Strings (Explanation + Code: LeetCode 2223)Prepflix · 9:18 · 388 views
2223. Sum of Scores of Built Strings (Hard) || LeetCode The Hard WayLeetCode The Hard Way · 4:35 · 195 views
The problem
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 <= 105sconsists of lowercase English letters.
Approach overview
Problem Overview: You receive a string s. For every suffix starting at index i, compute the length of the longest common prefix between s and s[i:]. The score of the string is the sum of all these prefix matches. The task is to compute this total efficiently.
Approach 1: Naive Comparison Approach (Time: O(n^2), Space: O(1))
The straightforward method compares the original string with every suffix. For index i, start two pointers: one at 0 and another at i. Increment both pointers while characters match to measure the longest common prefix length. Add this length to the total score. This requires scanning potentially the rest of the string for every starting position, which leads to quadratic time in the worst case. The approach is simple and useful for understanding the definition of the score, but it becomes too slow when the string length approaches the problem constraints.
Approach 2: Optimized Z-Algorithm Approach (Time: O(n), Space: O(n))
The optimal solution uses the Z-algorithm, a classic technique from string matching. The Z-array stores the length of the longest substring starting at index i that matches the prefix of the string. This is exactly the value required for each suffix comparison in the problem.
The algorithm maintains a window [L, R] representing the rightmost segment where a prefix match has already been computed. For each index, reuse previously computed values if the index falls inside this window. Otherwise, expand the match manually by comparing characters. This reuse avoids redundant comparisons and ensures linear processing. The final score is simply the sum of all Z values plus n (since the full string matches itself).
This technique appears frequently in advanced string problems and competes with methods like rolling hash or suffix arrays. Z-algorithm is preferred here because it computes prefix matches for every position in a single pass without hashing or binary search.
Recommended for interviews: Interviewers expect the Z-algorithm solution. The brute force approach shows you understand the definition of the score and prefix comparisons. The optimized solution demonstrates knowledge of linear-time string matching techniques and the ability to avoid repeated comparisons, which is the real signal of algorithmic skill.
Approach 1: Naive Comparison Approach
In this approach, we iteratively calculate the longest common prefix for each substring si with the full string s. We start from each position i of the string and compare it with the beginning of the string, checking for matching prefixes. This approach takes a direct comparison route and is easy to understand but can be improved in terms of efficiency.
def sum_scores(s):
n = len(s)
total_score = 0
for i in range(n):
score = 0
for j in range(n - i):
if s[j] == s[i + j]:
score += 1
else:
break
total_score += score
return total_score
# Example usage
print(sum_scores("babab")) # Output: 9public class Main {
public static int sumScores(String s) {
int n = s.length();
int totalScore = 0;
for (int i = 0; i < n; ++i) {
int score = 0;
for (int j = 0; i + j < n && s.charAt(j) == s.charAt(i + j); ++j) {
score++;
}
totalScore += score;
}
return totalScore;
}
public static void main(String[] args) {
System.out.println(sumScores("babab")); // Output: 9
}
}#include <iostream>
#include <string>
int sumScores(std::string s) {
int n = s.length();
int totalScore = 0;
for (int i = 0; i < n; ++i) {
int score = 0;
for (int j = 0; i + j < n && s[j] == s[i + j]; ++j) {
score++;
}
totalScore += score;
}
return totalScore;
}
int main() {
std::cout << sumScores("babab") << std::endl; // Output: 9
return 0;
}function sumScores(s) {
const n = s.length;
let totalScore = 0;
for (let i = 0; i < n; i++) {
let score = 0;
for (let j = 0; j < n - i && s[j] === s[i + j]; j++) {
score++;
}
totalScore += score;
}
return totalScore;
}
console.log(sumScores("babab")); // Output: 9#include <stdio.h>
#include <string.h>
int sumScores(char *s) {
int n = strlen(s);
int totalScore = 0;
for (int i = 0; i < n; ++i) {
int score = 0;
for (int j = 0; i + j < n && s[j] == s[i + j]; ++j) {
score++;
}
totalScore += score;
}
return totalScore;
}
int main() {
printf("%d\n", sumScores("babab")); // Output: 9
return 0;
}using System;
public class Program {
public static int SumScores(string s) {
int n = s.Length;
int totalScore = 0;
for (int i = 0; i < n; ++i) {
int score = 0;
for (int j = 0; i + j < n && s[j] == s[i + j]; ++j) {
score++;
}
totalScore += score;
}
return totalScore;
}
public static void Main() {
Console.WriteLine(SumScores("babab")); // Output: 9
}
}This Python code leverages slicing and direct index comparison to find and sum scores for string prefixes. It calculates matches for every possible prefix length.
Time Complexity: O(n^2); Space Complexity: O(1)
Approach 2: Optimized Z-Algorithm Approach
Instead of recalculating the prefix scores repeatedly, we utilize the Z-algorithm, which is efficient for pattern matching problems. The Z-array for a string stores the length of the longest substring starting from position i that is also a prefix of the string. With this pre-computed array, we can quickly determine the score for each si without redundant comparisons.
def calculate_z(s):
n = len(s)
Z = [0] * n
L, R, K = 0, 0, 0
for i in range(1, n):
if i > R:
L, R = i, i
while R < n and s[R] == s[R - L]:
R += 1
Z[i] = R - L
R -= 1
else:
K = i - L
if Z[K] < R - i + 1:
Z[i] = Z[K]
else:
L = i
while R < n and s[R] == s[R - L]:
R += 1
Z[i] = R - L
R -= 1
return Z
def sum_scores(s):
if not s: return 0
Z = calculate_z(s)
total_score = len(s) + sum(Z)
return total_score
# Example usage
print(sum_scores("babab")) # Output: 9public class Main {
public static int[] calculateZ(String s) {
int n = s.length();
int[] Z = new int[n];
int L = 0, R = 0;
for (int i = 1; i < n; ++i) {
if (i > R) {
L = R = i;
while (R < n && s.charAt(R) == s.charAt(R - L))
R++;
Z[i] = R - L;
R--;
} else {
int K = i - L;
if (Z[K] < R - i + 1) {
Z[i] = Z[K];
} else {
L = i;
while (R < n && s.charAt(R) == s.charAt(R - L))
R++;
Z[i] = R - L;
R--;
}
}
}
return Z;
}
public static int sumScores(String s) {
if (s.isEmpty()) return 0;
int[] Z = calculateZ(s);
int totalScore = s.length();
for (int z : Z) totalScore += z;
return totalScore;
}
public static void main(String[] args) {
System.out.println(sumScores("babab")); // Output: 9
}
}#include <iostream>
#include <vector>
std::vector<int> calculateZ(const std::string &s) {
int n = s.length();
std::vector<int> Z(n);
int L = 0, R = 0;
for (int i = 1; i < n; ++i) {
if (i > R) {
L = R = i;
while (R < n && s[R] == s[R - L])
R++;
Z[i] = R - L;
R--;
} else {
int K = i - L;
if (Z[K] < R - i + 1)
Z[i] = Z[K];
else {
L = i;
while (R < n && s[R] == s[R - L])
R++;
Z[i] = R - L;
R--;
}
}
}
return Z;
}
int sumScores(const std::string &s) {
if (s.empty()) return 0;
std::vector<int> Z = calculateZ(s);
int totalScore = s.length();
for (int z : Z) totalScore += z;
return totalScore;
}
int main() {
std::cout << sumScores("babab") << std::endl; // Output: 9
return 0;
}function calculateZ(s) {
const n = s.length;
const Z = new Array(n).fill(0);
let L = 0, R = 0;
for (let i = 1; i < n; i++) {
if (i > R) {
L = R = i;
while (R < n && s[R] === s[R - L]) {
R++;
}
Z[i] = R - L;
R--;
} else {
const K = i - L;
if (Z[K] < R - i + 1) {
Z[i] = Z[K];
} else {
L = i;
while (R < n && s[R] === s[R - L]) {
R++;
}
Z[i] = R - L;
R--;
}
}
}
return Z;
}
function sumScores(s) {
if (!s) return 0;
const Z = calculateZ(s);
let totalScore = s.length;
totalScore += Z.reduce((a, b) => a + b, 0);
return totalScore;
}
console.log(sumScores("babab")); // Output: 9#include <stdio.h>
#include <string.h>
void calculateZ(char *s, int *Z, int n) {
int L, R, K;
L = R = 0;
for (int i = 1; i < n; ++i) {
if (i > R) {
L = R = i;
while (R < n && s[R - L] == s[R])
R++;
Z[i] = R - L;
R--;
} else {
K = i - L;
if (Z[K] < R - i + 1)
Z[i] = Z[K];
else {
L = i;
while (R < n && s[R - L] == s[R])
R++;
Z[i] = R - L;
R--;
}
}
}
}
int sumScores(char *s) {
int n = strlen(s);
int Z[n];
calculateZ(s, Z, n);
int totalScore = n; // Include the score for the whole string
for (int i = 1; i < n; ++i) {
totalScore += Z[i];
}
return totalScore;
}
int main() {
printf("%d\n", sumScores("babab")); // Output: 9
return 0;
}using System;
public class Program {
public static int[] CalculateZ(string s) {
int n = s.Length;
int[] Z = new int[n];
int L = 0, R = 0;
for (int i = 1; i < n; ++i) {
if (i > R) {
L = R = i;
while (R < n && s[R] == s[R - L])
R++;
Z[i] = R - L;
R--;
} else {
int K = i - L;
if (Z[K] < R - i + 1) {
Z[i] = Z[K];
} else {
L = i;
while (R < n && s[R] == s[R - L])
R++;
Z[i] = R - L;
R--;
}
}
}
return Z;
}
public static int SumScores(string s) {
if (string.IsNullOrEmpty(s)) return 0;
int[] Z = CalculateZ(s);
int totalScore = s.Length;
foreach (int z in Z) totalScore += z;
return totalScore;
}
public static void Main() {
Console.WriteLine(SumScores("babab")); // Output: 9
}
}Python leverage the calculate_z function to efficiently compute the Z-array and sums these values to get the total score. This setup allows quick preprocessing of the string for score computation.
Time Complexity: O(n); Space Complexity: O(n)
Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Comparison Approach | Time Complexity: O(n^2); Space Complexity: O(1) |
| Optimized Z-Algorithm Approach | Time Complexity: O(n); Space Complexity: O(n) |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Comparison | O(n^2) | O(1) | Useful for understanding the definition of prefix scores or when input size is very small |
| Z-Algorithm | O(n) | O(n) | Best general solution; computes prefix matches for all suffixes efficiently |
Frequently asked questions
Is Sum of Scores of Built Strings easy or hard?
The problem is categorized as Hard because it requires knowledge of specialized string algorithms. Without the Z-algorithm or similar prefix-matching techniques, the naive solution becomes too slow for large inputs.
Sum of Scores of Built Strings Python/Java solution
Most implementations compute the Z-array in O(n) time and then sum the values. The logic is identical across Python, Java, C++, and other languages: maintain the [L, R] window, reuse previous matches when possible, and extend comparisons when needed.
How to solve Sum of Scores of Built Strings in O(n)?
Compute the Z-array for the string. Each Z[i] represents the length of the longest substring starting at i that matches the prefix. Summing all Z values and adding the string length gives the total score because the full string contributes n by definition.
What is the best approach for Sum of Scores of Built Strings?
The Z-algorithm is the most efficient approach. It computes the longest prefix match for every suffix in a single linear pass. This produces an overall time complexity of O(n) with O(n) extra space, making it ideal for large strings.
Is Sum of Scores of Built Strings asked at Google/Amazon/Meta?
Problems involving Z-algorithm, rolling hash, and prefix matching appear frequently in interviews at companies like Google, Amazon, and Meta. This specific problem tests understanding of advanced string matching techniques and linear-time optimizations.
What data structure is used in Sum of Scores of Built Strings?
The main structure is the Z-array, which stores prefix match lengths for each index. The algorithm also maintains two pointers representing a window of previously matched characters to reuse computations efficiently.
What is the time complexity of Sum of Scores of Built Strings?
The optimal solution runs in O(n) time using the Z-algorithm. A naive approach that compares the prefix with every suffix directly takes O(n^2) time in the worst case because each comparison may scan the remaining string.