Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumgreedy

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

Son görünüme kadar genişlet

Tested only

Time O(n)Space O(1)

Fikir. Karakter aralıklarında merge intervals ile aynı ruh.

Adım adım. “ababcbacadefegdehijhklij” → [9,7,8].

Trade-off’lar. İki geçiş O(n); ilk geçiş last[] kurar.

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

Şablon bağlantısı

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

Yansıma

90 saniyede hangi kalıp bunu ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?