2223. Sum of Scores of Built Strings LeetCode Solution
In this guide, you will get 2223. Sum of Scores of Built Strings LeetCode Solution with the best time and space complexity. The solution to Sum of Scores of Built Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2223. Sum of Scores of Built Strings LeetCode Solution in C++
class Solution {
public:
long long sumScores(string s) {
const int n = s.length();
// https://cp-algorithms.com/string/z-function.html#implementation
vector<int> z(n);
// [l, r] := the indices of the rightmost segment match
int l = 0;
int r = 0;
for (int i = 1; i < n; ++i) {
if (i < r)
z[i] = min(r - i, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
}
return accumulate(z.begin(), z.end(), 0L) + n;
}
}; /* code provided by PROGIEZ */
2223. Sum of Scores of Built Strings LeetCode Solution in Java
class Solution {
public long sumScores(String s) {
final int n = s.length();
// https://cp-algorithms.com/string/z-function.html#implementation
int[] z = new int[n];
// [l, r] := the indices of the rightmost segment match
int l = 0;
int r = 0;
for (int i = 1; i < n; ++i) {
if (i < r)
z[i] = Math.min(r - i, z[i - l]);
while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i]))
++z[i];
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
}
return Arrays.stream(z).asLongStream().sum() + n;
}
} // code provided by PROGIEZ
2223. Sum of Scores of Built Strings LeetCode Solution in Python
class Solution:
def sumScores(self, s: str) -> int:
n = len(s)
# https://cp-algorithms.com/string/z-function.html#implementation
z = [0] * n
# [l, r] := the indices of the rightmost segment match
l = 0
r = 0
for i in range(1, n):
if i < r:
z[i] = min(r - i, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] > r:
l = i
r = i + z[i]
return sum(z) + n # code by PROGIEZ
