1087. Distinct Pieces of Length K
A music app splits a song, written as a lowercase string s with one letter per note, into every possible run of exactly k consecutive notes. To measure how repetitive the song is, it counts how many different runs appear.
Return the number of distinct substrings of s whose length is exactly k. Two runs are the same when they spell the same string, no matter where in the song they start. If k is larger than the length of s, the answer is 0.
For example, in "xyxyxy" with k = 2 the windows are xy, yx, xy, yx, xy, so the answer is 2. Storing every window as a separate string wastes too much time and memory when k is large.
Example 1
- Input:
- s = "abcabcab", k = 3
- Output:
- 3
- Explanation:
The six windows of length 3 are abc, bca, cab, abc, bca, cab, which contain only three different strings.
Example 2
- Input:
- s = "aaaa", k = 2
- Output:
- 1
- Explanation:
Every window of length 2 is "aa", so there is just one distinct piece.
Example 3
- Input:
- s = "abcd", k = 5
- Output:
- 0
- Explanation:
The requested length is larger than the string itself, so no window exists and the answer is 0.
Constraints
1 ≤ s.length ≤ 3 * 105
1 ≤ k ≤ 106
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,000 msC++ 250 msJava 500 msJavaScript 500 msTypeScript 500 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)