Skip to main content

763. Partition Labels

medium

Split a string into as many parts as possible so that each letter appears in at most one part. A greedy sweep using last-occurrence indices — a perfect interval-merge variant.

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

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. 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".

Example 2

Input
s = "eccbbbbdec"
Output
[10]

Explanation: Every letter forces the whole string into one part.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

For each letter, find its LAST index in the string with a single pre-pass.

Hint 2

Sweep left to right tracking the maximum 'last index' seen so far for letters in the current window.

Hint 3

When the current position equals that maximum, close the partition and start a new one.

Solution approach

Reveal approach

Two-pass greedy. Pass 1: build last[c] = last index of character c. Pass 2: walk the string maintaining end = max(end, last[s[i]]). Whenever i == end, emit the size (i - start + 1) and reset start = i + 1. Each letter is visited twice — O(n) time. Extra space is O(1) because the last-index table holds at most 26 entries. The greedy choice is optimal because closing earlier would force a later partition to re-include the same letter, violating the constraint.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • greedy
  • two-pointers
  • interval-merging

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Partition Labels and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →