Partition Labels

Problem (restated)

Partition string so each letter appears in at most one part. Return sizes of parts as large/as many as possible (greedy max parts).

Intuition

Record last index of each char. Scan left→right expanding end to last[c]; when i==end, cut a part.

Approaches

export function partitionLabels(s: string): number[] {
  const last = Array(26).fill(0);
  for (let i = 0; i < s.length; i++) last[s.charCodeAt(i) - 97] = i;
  const res: number[] = [];
  let start = 0, end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last[s.charCodeAt(i) - 97]!);
    if (i === end) {
      res.push(end - start + 1);
      start = i + 1;
    }
  }
  return res;
}

export function partitionLabels(s: string): number[] {
  const last = Array(26).fill(0);
  for (let i = 0; i < s.length; i++) last[s.charCodeAt(i) - 97] = i;
  const res: number[] = [];
  let start = 0, end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last[s.charCodeAt(i) - 97]!);
    if (i === end) {
      res.push(end - start + 1);
      start = i + 1;
    }
  }
  return res;
}

Template connection

Greedy interval merge / span expansion.

Reflection

• Store each letter’s last index. A part grows until it has swallowed the last index of every letter already inside it.
• abab is one part. abc is three. When a part ends, the next part starts at that index.
• One repeated letter is a single part. The parts cut the string from start to end and do not overlap.