Prefix Echo Score
MediumTries & Strings
Problem
For a string s, the echo of a position i is the length of the longest common prefix of s and the suffix of s starting at i. The echo of position 0 is the whole length of s.
Return the sum of the echoes of all positions.
Example 1
- Input:
- s = "abab"
- Output:
- 6
Echoes: 4 (abab), 0 (bab), 2 (ab), 0 (b).
Example 2
- Input:
- s = "aaa"
- Output:
- 6
Echoes 3, 2, 1.
Example 3
- Input:
- s = "abc"
- Output:
- 3
Constraints
- 1 ≤ s.length ≤ 10^5
- Lowercase English letters only.
Hint
Show the first hint
Comparing each suffix with s from scratch is quadratic on strings like "aaaa...".
Walkthrough
How to approach it
01Clarify before coding
- Does position 0 count? Yes, with echo n.
- Can the answer exceed 32 bits? It is at most n(n + 1)/2 ≈ 5·10^9, so use a 64-bit or arbitrary-precision integer (JavaScript numbers are exact up to 2^53).
02Brute force
For every i, compare s[i..] with s character by character until a mismatch.
Cost: O(n²): about 5·10^9 comparisons on a string of 10^5 equal letters.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.