Partition Labels

medium

Partition string so each letter appears in at most one part

Partition Labels

Key Insight

Track last occurrence of each char. Extend partition until index equals end.

Step 1Track Last Occurrences
last: a=8, b=5, c=7
a
0
b
1
a
2
b
3
c
4
b
5
a
6
c
7
a
8

For "ababcbaca": a→8, b→5, c→7

1 / 5

Learn the Pattern

Two PointersUse two pointers to traverse an array or string, reducing time complexity from O(n^2) to O(n) for problems involving pairs or subarrays.
Practice the Code

Step-by-Step Walkthrough: Partition Labels

Track last occurrence of each char. Extend partition until index equals end.

  1. Track Last Occurrences

    For "ababcbaca": a→8, b→5, c→7

  2. Start Partition

    At i=0, char="a", last=8. End must be at least 8.

  3. Check All Chars

    All chars between 0-8 have last occurrence ≤ 8.

  4. Partition Complete

    When i reaches end (8), partition is complete. Size=9.

  5. Result

    Only one partition of size 9 for this example.