Partition Labels

Examples

Input: S = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]

The parts are "ababcbaca", "defegde", and "hijhklij". Splitting any finer would separate two occurrences of the same letter.

Input: S = "eccbbbbdec"
Output: [10]

Letter "e" appears at both index 0 and index 8, and other letters overlap with that range too, so the whole string must be one part.

Input: S = "abc"
Output: [1, 1, 1]

No letter repeats, so every character can be its own part.

Constraints

• 1 <= S.length <= 500

• S consists of lowercase English letters

Approach

A part is only valid once it stretches far enough to include the very last occurrence of every letter that shows up inside it - cutting it any shorter would strand a repeat of one of those letters in a later part. So first record, for every letter, the index of its last occurrence in the string.

Then greedily grow a window from left to right: as you extend the window's end, keep expanding it to the last occurrence of each new letter encountered. Once your current scan position reaches that end, you know no letter inside the window reappears later, so the window is a complete, valid part - close it and start a new one.

Solutions

Brute Force - Grow and Verify Each Part

For each starting position, keep extending the candidate part until no letter inside it appears again later in the string.

function partitionLabels(s) {
  const result = [];
  let start = 0;

  while (start < s.length) {
    let end = start;
    let i = start;
    while (i <= end) {
      const lastOccurrence = s.lastIndexOf(s[i]);
      end = Math.max(end, lastOccurrence);
      i++;
    }
    result.push(end - start + 1);
    start = end + 1;
  }
  return result;
}

Time: O(n^2) since lastIndexOf rescans the string for every character examined · Space: O(1) extra (excluding the output)

Optimal - Precompute Last Occurrences

Record each letter's last index up front in one pass. Then scan once, growing the current part's end to the last occurrence of every letter seen, and cutting a part whenever the scan catches up to that end.

function partitionLabels(s) {
  const lastIndex = new Map();
  for (let i = 0; i < s.length; i++) lastIndex.set(s[i], i);

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

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

Time: O(n) · Space: O(1) since there are at most 26 lowercase letters