medium

Partition Labels

Split a string into the most parts possible so each letter appears in only one part.

1. Define the problem

Partition Labels

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part . Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s. Return a list of integers representing the size of these parts. Precompute the last index each letter appears at , then scan the string with a pointer tracking the farthest last-occurrence seen so far as the current partition's end boundary — when the scan reaches that boundary, close the partition.

Constraints

  • 1 ≤ s.length ≤ 500
  • s consists of lowercase English letters.

Example

Inputs = "ababcbacadefegdehijhklij"
Output[9, 7, 8]

Explanation The partition is "ababcbaca", "defegde", "hijhklij" — each letter appears in only one of these parts, and their sizes are 9, 7, and 8.

2. Know the words first

In plain terms

Partition
Splitting a string into consecutive, non-overlapping pieces that together make up the whole string again, like cutting a rope into segments without removing any of it.
3. Visualize the solution

Track the farthest last-occurrence as the partition boundary

Track the farthest last-occurrence as the partition boundary
Statusinit

i=0 (a): end becomes max(0, last[a]=8) = 8.

What happens in this step

i = 0 (letter 'a')
last['a'] = 8
end = max(0, 8) = 8

We start scanning at index 0. Since 'a' last appears at index 8, the current partition's boundary end is pushed out to 8.
Step 1 of 4

Steps to visualize

  1. Precompute the last index at which each letter appears in the string.
  2. Scan forward, updating end to the farthest last-occurrence seen among the letters visited so far.
  3. When the scan pointer reaches end, the current partition is complete — record its length.
  4. Start the next partition right after the boundary and repeat until the string is exhausted.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Track the farthest last-occurrence as the partition boundary
Statusinit

i=0 (a): end becomes max(0, last[a]=8) = 8.

What happens in this step

i = 0 (letter 'a')
last['a'] = 8
end = max(0, 8) = 8

We start scanning at index 0. Since 'a' last appears at index 8, the current partition's boundary end is pushed out to 8.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function partitionLabels(s) {
  const last = {};
  for (let i = 0; i < s.length; i++) {
    last[s[i]] = i;
  }

  const result = [];
  let start = 0;
  let end = 0;

  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last[s[i]]);
    if (i === end) {
      result.push(end - start + 1);
      start = i + 1;
    }
  }

  return result;
}
Time
O(n)
Space
O(1) (fixed alphabet size for the last-occurrence map)
6. Test cases

Test cases

InputExpectedCovers
s = "ababcbacadefegdehijhklij"[9, 7, 8]example from the docstring
s = "a"[1]smallest valid input: a single character
s = "abcdef"[1, 1, 1, 1, 1, 1]no character repeats, so every partition has length 1
s = "eccbbbbdec"[10]the whole string is a single partition
s = "eeddffgg"[2, 2, 2, 2]every letter appears exactly twice, adjacent to itself
s = "aaaaaaaa"[8]every character is the same letter

Keep reading