# Sum of Scores of Built Strings **Difficulty:** HARD [External](https://leetcode.com/problems/sum-of-scores-of-built-strings) Canonical: https://scaleengineer.com/dsa/problems/sum-of-scores-of-built-strings **Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function) **Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search) **Data structures:** String, Suffix Array --- ## 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 <= 105` * `s` consists of lowercase English letters. # Approaches ## Brute Force Iteration This approach directly implements the problem description. We iterate through each possible suffix of the string `s`, and for each suffix, we compare it character by character with the original string `s` to find the length of the longest common prefix (LCP). The sum of these lengths is the final answer. **Time:** O(n^2), where n is the length of the string. The nested loops lead to a quadratic number of character comparisons in the worst case (e.g., a string of all identical characters). · **Space:** O(1), as we only use a few variables to store the counts and indices, not dependent on the input string size. **Pros:** Simple to understand and implement.; Requires no extra space. **Cons:** Inefficient for large strings. The quadratic time complexity will lead to a "Time Limit Exceeded" error on platforms like LeetCode for the given constraints. ### Explanation We iterate from `i = 0` to `n-1`, where `n` is the length of the string `s`. Each `i` represents the starting index of a suffix `s[i:]`. For each suffix, we start a nested loop to compare `s[i+j]` with `s[j]` for `j = 0, 1, 2, ...`. We count the number of matching characters from the beginning. This count is the score for the suffix starting at `i`. We stop comparing and break the inner loop as soon as a mismatch is found or the end of the suffix is reached. The scores for all suffixes are summed up to get the final result. For `s = "babab"`, we would first compare "babab" with "babab" (LCP=5), then "abab" with "babab" (LCP=0), then "bab" with "babab" (LCP=3), and so on. ```java class Solution { public long sumScores(String s) { int n = s.length(); long totalScore = 0; for (int i = 0; i < n; i++) { int currentScore = 0; for (int j = 0; i + j < n; j++) { if (s.charAt(j) == s.charAt(i + j)) { currentScore++; } else { break; } } totalScore += currentScore; } return totalScore; } } ``` ### Algorithm - Initialize `totalScore` to 0. - Get the length of the string, `n`. - Loop with an index `i` from 0 to `n-1`. This `i` represents the start of the suffix. - Initialize `currentScore` to 0. - Loop with an index `j` from 0, as long as `i+j` is within the bounds of the string. - If `s.charAt(j)` is equal to `s.charAt(i+j)`, increment `currentScore`. - Otherwise, break the inner loop. - Add `currentScore` to `totalScore`. - Return `totalScore`. ## String Hashing (Rabin-Karp) with Binary Search To optimize the LCP calculation for each suffix, we can use string hashing. We precompute polynomial rolling hashes for all prefixes of the string `s`. This allows us to find the hash of any substring in O(1) time. For each suffix, we can then use binary search on the possible LCP length. In each step of the binary search, we check if the hash of the prefix of `s` matches the hash of the prefix of the current suffix. **Time:** O(n log n). Precomputation takes O(n). The main loop runs `n` times, and each iteration involves a binary search that takes O(log n) time. · **Space:** O(n) to store the precomputed prefix hashes and powers of the base. **Pros:** Significantly faster than the brute-force approach.; Can pass the time limits for the given constraints. **Cons:** More complex to implement than the brute-force approach.; Relies on hashing, which has a theoretical (though very small) probability of collision. Using two hash functions makes this probability negligible for typical contest constraints.; Requires extra space for storing hash values and powers. ### Explanation The core idea is to speed up the comparison of two substrings. Instead of character-by-character comparison, we compare their hash values. First, we precompute the hashes of all prefixes of `s`. We also precompute powers of a chosen base `p`. Using two different hash functions (different base and modulus) is recommended to minimize collisions. Then, for each suffix starting at index `i`, we want to find the maximum length `k` such that `s[0...k-1]` is the same as `s[i...i+k-1]`. We can binary search for this `k` in the range `[0, n-i]`. For a given `mid` length in the binary search, we calculate the hash of `s[0...mid-1]` and `s[i...i+mid-1]` in O(1) time using our precomputed values. If the hashes match, we try a larger length (`low = mid + 1`); otherwise, we try a smaller length (`high = mid - 1`). The largest `k` found for each `i` is the score, which we add to the total. ```java class Solution { public long sumScores(String s) { int n = s.length(); long p1 = 31, m1 = 1_000_000_007; long p2 = 37, m2 = 1_000_000_009; long[] p_pow1 = new long[n + 1]; long[] p_pow2 = new long[n + 1]; long[] h1 = new long[n + 1]; long[] h2 = new long[n + 1]; p_pow1[0] = 1; p_pow2[0] = 1; for (int i = 0; i < n; i++) { p_pow1[i + 1] = (p_pow1[i] * p1) % m1; p_pow2[i + 1] = (p_pow2[i] * p2) % m2; h1[i + 1] = (h1[i] * p1 + (s.charAt(i) - 'a' + 1)) % m1; h2[i + 1] = (h2[i] * p2 + (s.charAt(i) - 'a' + 1)) % m2; } long totalScore = 0; for (int i = 0; i < n; i++) { int low = 0, high = n - i, lcp = 0; while (low <= high) { int mid = low + (high - low) / 2; if (mid == 0) { low = mid + 1; continue; } long hash1_s1 = h1[mid]; long hash2_s1 = h2[mid]; long hash1_s2 = (h1[i + mid] - (h1[i] * p_pow1[mid]) % m1 + m1) % m1; long hash2_s2 = (h2[i + mid] - (h2[i] * p_pow2[mid]) % m2 + m2) % m2; if (hash1_s1 == hash1_s2 && hash2_s1 == hash2_s2) { lcp = mid; low = mid + 1; } else { high = mid - 1; } } totalScore += lcp; } return totalScore; } } ``` ### Algorithm - Choose two pairs of base and modulus `(p1, m1)` and `(p2, m2)` for rolling hash to reduce collisions. - Precompute powers of `p1` and `p2`. - Precompute prefix hashes for the string `s` using both hash functions. This takes O(n) time. - Initialize `totalScore` to 0. - Loop with an index `i` from 0 to `n-1`. - Perform a binary search for the LCP length `k` in the range `[0, n-i]`. - For a given length `mid` in the binary search: - Calculate the hash of the prefix `s[0...mid-1]`. - Calculate the hash of the substring `s[i...i+mid-1]`. - If the hashes from both hash functions match, it means the substrings are likely identical. We search for a longer LCP by setting `low = mid + 1` and updating the potential LCP length. - If they don't match, we search for a shorter LCP by setting `high = mid - 1`. - Add the found LCP length to `totalScore`. - Return `totalScore`. ## Z-Algorithm This problem is a direct application of the Z-algorithm. The Z-algorithm computes a Z-array for a string `s`, where `Z[i]` is the length of the longest common prefix between `s` and the suffix of `s` starting at index `i`. The sum of all values in the Z-array is precisely the answer to the problem. The Z-algorithm can compute this array in linear time. **Time:** O(n). The algorithm processes the string in a single pass. Although there's a nested `while` loop, the total number of character comparisons is bounded by `2n` because the right pointer `r` only moves forward. · **Space:** O(n) to store the Z-array. **Pros:** Most efficient solution with linear time complexity.; Elegant and tailored specifically for this type of LCP problem. **Cons:** The algorithm can be non-intuitive to understand and implement correctly without prior knowledge. ### Explanation The Z-array `z` for a string `s` of length `n` is an array of length `n` where `z[i]` is the length of the LCP between `s` and `s[i:]`. The score for the suffix `s[i:]` is exactly `z[i]`. Therefore, the problem reduces to computing the Z-array and summing its elements. The Z-algorithm computes this array efficiently in O(n) time by maintaining a "Z-box" `[l, r]`, which is the interval corresponding to the prefix match that extends furthest to the right. When computing `z[i]`, if `i` is within the current Z-box `[l, r]`, we can use the already computed `z[i-l]` value to get an initial estimate for `z[i]`, avoiding redundant comparisons. If `i` is outside the box, we compute `z[i]` by naively comparing characters. The key insight is that the total number of character comparisons is linear because the right boundary `r` of the Z-box only moves forward. After computing the Z-array, we simply sum up all its elements. Note that `z[0]` is the LCP of `s` with itself, which is `n`. ```java class Solution { public long sumScores(String s) { int n = s.length(); int[] z = new int[n]; long totalScore = n; // z[0] is n, add it upfront int l = 0, r = 0; for (int i = 1; i < n; i++) { // If i is inside the current Z-box [l, r] if (i <= r) { z[i] = Math.min(r - i + 1, z[i - l]); } // Naively extend the match while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) { z[i]++; } // If we found a Z-box that extends beyond the current r, update l and r if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; } totalScore += z[i]; } return totalScore; } } ``` ### Algorithm - Create an integer array `z` of size `n`. - Initialize `l = 0`, `r = 0` which define the boundaries of the current rightmost Z-box. - Loop with `i` from 1 to `n-1`: - If `i` is within the current Z-box (`i <= r`), we can initialize `z[i]` to `min(r - i + 1, z[i - l])`. This leverages previous computations. - Expand `z[i]` by comparing `s[z[i]]` with `s[i + z[i]]` until a mismatch or the end of the string is found. - If the new match `s[i...i+z[i]-1]` extends beyond the current Z-box (`i + z[i] - 1 > r`), update `l` to `i` and `r` to `i + z[i] - 1`. - The score for the full string `s` (i.e., `z[0]`) is `n`. - The total score is the sum of `n` and all `z[i]` for `i` from 1 to `n-1`.