909. Distinct Pieces
A bead-maker writes the colour of each bead on a necklace strand as one lowercase letter, giving the string s. A piece is any non-empty run of consecutive beads. Two pieces that spell the same string are the same piece, even if they come from different places on the strand.
Return how many different pieces the strand contains. For example, a strand aa has two different pieces, a and aa.
Listing every piece in a set is too slow and too big for long strands, so aim for about O(n) time and O(n) space (times the small alphabet size), where n is the length of s. The answer fits in a 32-bit integer.
Example 1
- Input:
- s = "zzyzz"
- Output:
- 11
- Explanation:
The string has 11 different non-empty contiguous pieces when equal pieces are counted once.
Example 2
- Input:
- s = "kayakk"
- Output:
- 18
- Explanation:
The string has 18 different non-empty contiguous pieces when equal pieces are counted once.
Constraints
1 ≤ s.length ≤ 50000
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 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)