594. No Repeat Pieces
A label printer receives a long strip of lowercase letters, given as the string s. The strip must be cut into consecutive pieces, with every character belonging to exactly one piece and the order of characters never changed. A piece is acceptable only if no letter appears twice inside it; the same letter may of course appear in different pieces.
Return the smallest number of pieces needed. For example, a strip that has no repeated letters at all needs just one piece. A valid cutting always exists because a single character is always an acceptable piece. Your solution should run in O(n) time and O(1) extra space, since the alphabet has only 26 letters.
Example 1
- Input:
- s = "abcabc"
- Output:
- 2
- Explanation:
The strip splits as abc|abc, and one piece is impossible because letters repeat, so the answer is 2.
Example 2
- Input:
- s = "qwerty"
- Output:
- 1
- Explanation:
All letters are different, so the whole strip is a single valid piece.
Example 3
- Input:
- s = "aabb"
- Output:
- 3
- Explanation:
Cuts are forced between the equal neighbours, giving a|ab|b, which is 3 pieces.
Constraints
1 ≤ s.length ≤ 200000sconsists of lowercase English letters only.
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,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)