832. Wraparound Substrings
Picture the alphabet written on an endless ribbon that never stops: ...abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc..., with z followed by a again. A string "fits the ribbon" if it appears as a contiguous piece of it.
Given a string s of lowercase letters, return how many different non-empty substrings of s fit the ribbon. Equal text counts once, however many times it occurs in s. The answer fits in a 32-bit integer. Aim for time O(n) and constant extra space.
Example 1
- Input:
- s = "tuvwtu"
- Output:
- 10
- Explanation:
Distinct substrings that follow the alphabet loop:
t, u, v, w, tu, uv, vw, tuv, uvw, tuvw, so the answer is10.
Example 2
- Input:
- s = "pqpqr"
- Output:
- 6
- Explanation:
Repeated pieces such as
pqare counted once; the total is6.
Example 3
- Input:
- s = "xyzabc"
- Output:
- 21
- Explanation:
The run crosses from z back to a, giving
21different substrings.
Constraints
1 ≤ s.length ≤ 105
s consists of lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)