Scale Engineer

Sum of Scores of Built Strings

Hard
#2026Time: 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.
Patterns
String MatchingRolling HashHash Function
Algorithms
Binary Search
Data structures
StringSuffix Array

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem