Optimal Partition of String

Medium Topics Company Tags

Split s into contiguous, nonempty pieces so that no piece contains a repeated letter. Every character must occur in exactly one piece. Return the smallest possible number of pieces.

Example 1:

Input: s = "a"

Output: 1

Explanation: The only character forms one piece, "a".

Example 2:

Input: s = "ab"

Output: 1

Explanation: The letters in "ab" are already distinct, so the whole string can stay in one piece.

Example 3:

Input: s = "aa"

Output: 2

Explanation: The two occurrences of "a" cannot share a piece. Split the string into "a" and "a".

Constraints:

  • 1 <= s.length <= 100000
  • Only lowercase English letters occur.


Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.