Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Greedy

Guide 6 of 6 · Path 6 of 6

← PreviousNext pattern: One-Dimensional DP →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumgreedy

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

Expand to last occurrence

Tested only
Time O(n)Space O(1)

Idea. Same spirit as merge intervals on char spans.

Walkthrough. “ababcbacadefegdehijhklij” → [9,7,8].

Trade-offs. Two-pass O(n); first pass builds last[].

Solution
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