Sum Of Scores Of Built Strings · Interview Problem

Leetcode

Medium

Strings

Arrays

Google

Sum Of Scores Of Built Strings

Compute the total score of a string by summing the lengths of the longest common prefix between the string and each of its suffixes.

Acceptance 0%

Start Practice

Problem Statement

Given a string $s$ , define the score of a suffix $s[i:]$ as the length of the longest common prefix between $s$ and $s[i:]$ . The score of the whole string is the sum of the scores of all suffixes.

Your task is to return that total score.

This is a string-matching style problem: for every starting position, compare the suffix against the original string and accumulate the prefix match length.

Input Format

A single string $s$ .
The string contains only lowercase English letters.

Output Format

Return one integer: the sum of scores of all suffixes of $s$ .

Constraints

$1 \le |s| \le 10^5$
$s$ contains only lowercase English letters.
The answer may not fit in 32-bit integer arithmetic.

Examples

Sample cases returned by the problem API.

Example 1

Input

s = "babab"

Output

Explanation

Suffix scores are:

"babab" vs "babab" -> 5
"abab" vs "babab" -> 0
"bab" vs "babab" -> 3
"ab" vs "babab" -> 0
"b" vs "babab" -> 1 Total = 5 + 0 + 3 + 0 + 1 = 9.

Example 2

Input

s = "aaaaa"

Output

Explanation

Every suffix matches the full prefix as much as possible: 5 + 4 + 3 + 2 + 1 = 15.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress