Welcome to Subscribe On Youtube

2223. Sum of Scores of Built Strings

Description

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.

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public long sumScores(String s) {
          int n = s.length();
          int[] z = new int[n];
          for (int i = 1, l = 0, r = 0; i < n; ++i) {
              if (i <= r) {
                  z[i] = Math.min(r - i + 1, z[i - l]);
              }
              while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {
                  ++z[i];
              }
              if (i + z[i] - 1 > r) {
                  l = i;
                  r = i + z[i] - 1;
              }
          }
          long ans = n;
          for (int x : z) {
              ans += x;
          }
          return ans;
      }
  }
  
  

• class Solution {
  public:
      long long sumScores(string s) {
          int n = s.size();
          vector<int> z(n);
          for (int i = 1, l = 0, r = 0; i < n; ++i) {
              if (i <= r) {
                  z[i] = min(r - i + 1, z[i - l]);
              }
              while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
                  ++z[i];
              }
              if (i + z[i] - 1 > r) {
                  l = i;
                  r = i + z[i] - 1;
              }
          }
          return n + accumulate(z.begin(), z.end(), 0LL);
      }
  };
  
  

• class Solution:
      def sumScores(self, s: str) -> int:
          n = len(s)
          z = [0] * n
          l = r = 0
          for i in range(1, n):
              if i <= r:
                  z[i] = min(r - i + 1, z[i - l])
              while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                  z[i] += 1
              if i + z[i] - 1 > r:
                  l, r = i, i + z[i] - 1
          return n + sum(z)
  
  

• func sumScores(s string) int64 {
  	n := len(s)
  	z := make([]int, n)
  	for i, l, r := 1, 0, 0; i < n; i++ {
  		if i <= r {
  			z[i] = min(r-i+1, z[i-l])
  		}
  		for i+z[i] < n && s[z[i]] == s[i+z[i]] {
  			z[i]++
  		}
  		if i+z[i]-1 > r {
  			l, r = i, i+z[i]-1
  		}
  	}
  	ans := int64(n)
  	for _, x := range z {
  		ans += int64(x)
  	}
  	return ans
  }
  
  

All Problems

All Solutions