Partition Labels

Problem (yeniden ifade)

Dizeyi her harf en fazla bir parçada görünecek şekilde böl. Parça boyutlarını (mümkün olduğunca çok parça / greedy) döndür.

Sezgi

Her karakterin son indeksini kaydet. Soldan sağa tararken end’i last[c]’ye genişlet; i==end olunca parça kes.

Yaklaşımlar

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;
}

Şablon bağlantısı

Greedy aralık birleştirme / span genişletme.

Yansıma

• Her harfin son indeksini tut. Parça, içindeki harflerin sonunu yutana kadar uzar.
• abab tek parça. abc üç parça. Parça bitince yeni başlangıç o indeks.
• Tüm dizgi aynı harf: bir parça. Parçalar dizgiyi baştan sona böler, örtüşmez.