1083. Smallest Period
A tile factory prints a long border strip from a repeating stencil. The strip is described by a lowercase string s, one letter per cell. The stencil is laid again and again from the left edge, and the last copy may be cut off in the middle.
Formally, a number p with 1 <= p <= s.length is a period of s if s[i] == s[i + p] for every index i with i + p < s.length. The value s.length is always a period.
Return the smallest period of s, which is the length of the shortest stencil that can produce the strip. For example, "qrsqrsq" has period 3, because the strip is qrs repeated with a partial third copy, while "qqrqq" has period 3 as well.
Example 1
- Input:
- s = "abcabcab"
- Output:
- 3
- Explanation:
Shifting by 3 lines every letter up with the letter 3 places later (the last tile is only partly shown), and no shift of 1 or 2 does.
Example 2
- Input:
- s = "abcd"
- Output:
- 4
- Explanation:
No letter repeats, so only a shift by the whole length works.
Example 3
- Input:
- s = "zzzzz"
- Output:
- 1
- Explanation:
Every letter equals its right neighbour, so a shift of 1 is enough.
Constraints
1 ≤ s.length ≤ 5 * 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(n)