LeetCode 763 Partition Labels - Example and Complexity Analysis

Trace s = "abab".

Last occurrence: a→2, b→3.

i=0 ('a'): start=0, end=max(0, 2)=2. i=1 ('b'): end=max(2, 3)=3. i=2 ('a'): end=max(3, 2)=3. i=3 ('b'): i==end. Partition ends! Size = 3-0+1 = 4.

Result: [4]. (Entire string is one partition.)

Trace s = "abc". Last: a→0, b→1, c→2. i=0: end=0, i==end. Partition [0,0]. Size 1. i=1: start=1, end=1, i==end. Size 1. i=2: start=2, end=2, i==end. Size 1.

Result: [1,1,1].

$O(n)$ time (two passes). $O(1)$ space (26 letters max).