Skip to main content

763. Partition Labels

mediumAsked at Amazon

Partition a string into as many parts as possible so that each letter appears in at most one part. Amazon asks this to test whether you reach for the greedy 'extend partition until furthest end' pattern.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE I/II onsite reports cite this as a recurring greedy problem.
  • Blind (2025-10)— Recurring Amazon interview problem.

Problem

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.

Constraints

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

Examples

Example 1

Input
s = "ababcbacadefegdehijhklij"
Output
[9,7,8]

Explanation: The partition is "ababcbaca", "defegde", "hijhklij". A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.

Example 2

Input
s = "eccbbbbdec"
Output
[10]

Approaches

1. Last-occurrence map + greedy sweep (optimal)

Precompute lastIdx[c] for each char. Sweep s; extend current partition end to max(end, lastIdx[s[i]]). When i reaches end, close partition.

Time
O(n)
Space
O(1) for alphabet
function partitionLabels(s) {
  const lastIdx = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    lastIdx[s.charCodeAt(i) - 97] = i;
  }
  const result = [];
  let start = 0, end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, lastIdx[s.charCodeAt(i) - 97]);
    if (i === end) {
      result.push(end - start + 1);
      start = i + 1;
    }
  }
  return result;
}

Tradeoff: Linear. The 'extend end' greedy is correct because every char we see forces the partition to extend to that char's last occurrence — otherwise we'd split the char across partitions.

Amazon-specific tips

Amazon interviewers grade this on whether you can articulate the greedy invariant: 'For every char in the current partition, the partition must extend at least to that char\'s LAST occurrence. So I track the max last-occurrence as I sweep, and close the partition when i matches it.' Without that articulation, the algorithm looks like a hack.

Common mistakes

  • Resetting end on each iteration instead of taking max (would shrink the partition prematurely).
  • Off-by-one when computing the partition size (end - start + 1).
  • Trying to use a hash set of seen chars — works but is more complicated than necessary.

Follow-up questions

An interviewer at Amazon may pivot to one of these next:

  • What if you wanted the MINIMUM number of partitions (different problem)?
  • What if some chars could appear in multiple partitions (relax the constraint)?
  • What if the alphabet were unbounded?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is greedy correct here?

Each char's last occurrence MUST be in the same partition as its first. So the partition end is the max of all last-occurrences within the current partition. Once i reaches that max, no future char in this partition can extend further.

Why precompute lastIdx instead of computing on the fly?

Each lookup must be O(1). Precomputing gives constant-time access during the sweep. Recomputing on each iteration would be O(n^2).

Practice these live with InterviewChamp.AI

Drill Partition Labels and other Amazon interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →