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 Sam K., 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

More Strings practice problems

See all Strings problems →