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.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Sum of Scores of Built Strings solution in C++
  4. Sum of Scores of Built Strings solution in Java
  5. Sum of Scores of Built Strings solution in Python
  6. Additional Resources
2223. Sum of Scores of Built Strings LeetCode Solution image

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:

See also  3233. Find the Count of Numbers Which Are Not Special LeetCode Solution

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

Additional Resources

See also  3179. Find the N-th Value After K Seconds LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.