Wawancara Koding: Bagaimana Cara Menyelesaikan Minimum Window Substring?

Masalah dan Kapan Ini Berlaku

Diberikan string s dan t, temukan substring kontinu terpendek dari s yang memuat setiap karakter dari t setidaknya sebanyak kemunculannya di t. Pencocokan bersifat peka huruf besar/kecil (case-sensitive). Contohnya:

s = "ADOBECODEBANC"
t = "ABC"
output = "BANC"

Jika t = "AABC", jendela kandidat membutuhkan setidaknya dua karakter A, satu B, dan satu C. Pengecekan keanggotaan himpunan (set-membership) akan kehilangan persyaratan multiplisitas ini, yang merupakan kesalahan semantik paling umum dalam masalah ini.

Batasannya adalah 1 <= s.length, t.length <= 100000, dan kedua string hanya berisi huruf alfabet Inggris besar dan kecil. Jika jawaban ada, jawaban terpendek tersebut bersifat unik. Kembalikan string kosong jika tidak ada jendela yang mencakup t. Implementasi di bawah ini juga menangani t yang kosong dan s yang lebih pendek dari t secara defensif, meskipun input tersebut berada di luar batasan standar.

Catatan wawancara rekayasa perangkat lunak publik terbaru masih menampilkan Minimum Window Substring, termasuk variasi di mana t tidak memiliki karakter duplikat. Platform koding berbahasa Inggris maupun Mandarin juga mempertahankan masalah ini. Keterampilan intinya adalah mengubah pencarian interval minimum global menjadi state yang dipertahankan secara inkremental, sehingga kategori yang tepat adalah coding; bahasa contoh tidak mengubah klasifikasi tersebut.

Apa yang Dinilai oleh Pewawancara

Sinyal pertama adalah pemodelan yang presisi. Jawaban yang kuat menyatakan "memuat t" sebagai batasan frekuensi: untuk setiap karakter target c, jendela saat ini harus memenuhi window[c] >= need[c]. Sekadar mengatakan bahwa semua karakter target telah muncul tidak dapat menangani t = "AA".

Sinyal kedua adalah mengenali monotonisitas di balik baseline kuadratik. Menggeser batas kanan hanya menambahkan karakter, sehingga jendela yang valid akan tetap valid saat diperluas. Untuk batas kanan yang tetap, menggeser batas kiri akan menghapus karakter. Setelah jendela valid, jendela dapat dikontraksi hingga tepat menjadi tidak valid, sembari mencatat kandidat yang lebih pendek di sepanjang proses.

Sinyal ketiga adalah mengompresi pengecekan validitas. Memindai seluruh tabel frekuensi pada setiap pergeseran akan menghilangkan batas linear. Implementasi menggunakan formed untuk jumlah kelas karakter target yang frekuensi kebutuhannya telah tercapai, dengan required = need.size. formed bertambah ketika frekuensi pertama kali menjadi sama dengan kebutuhannya dan berkurang ketika penghapusan membuatnya berada di bawah kebutuhan tersebut. Salinan berlebih tidak dihitung dua kali.

Terakhir, kandidat harus menjustifikasi kebenaran dan kondisi batas: mengapa jendela valid terpendek untuk setiap batas kanan diperiksa, mengapa batas kiri yang dibuang tidak dapat menghasilkan kandidat masa depan yang lebih baik, dan mengapa setiap pointer bergerak paling banyak s.length kali.

Pertanyaan yang Perlu Diklarifikasi Sebelum Menjawab

• Apakah pencocokan bersifat case-sensitive? Ya, dalam kasus ini. Jika pencocokan mengabaikan huruf besar/kecil, tentukan normalisasinya terlebih dahulu; normalisasi dapat mengubah

pemetaan kembali ke indeks pada string asli.

• Apakah "memuat" mempertahankan urutan dari t? Tidak. Masalah ini hanya memerlukan cakupan frekuensi. Mengharuskan urutan menghasilkan masalah

Minimum Window Subsequence, yang mana kondisi validitas ini tidak berlaku.

• Apakah karakter target duplikat dihitung secara terpisah? Ya. t = "AABC" memerlukan dua karakter A, yang secara langsung mendasari kebutuhan

frequency map.

• Apa yang terjadi jika terdapat beberapa jendela terpendek dengan panjang yang sama? Masalah standar menjamin keunikan. Tanpa jaminan tersebut, implementasi

ini mengembalikan jendela terpendek yang paling awal muncul karena ia hanya melakukan pembaruan pada panjang yang strictly lebih kecil.

• Apa set karakternya? Input berupa huruf alfabet Inggris, sehingga pengindeksan unit kode UTF-16 JavaScript tidak akan memecah karakter yang

diizinkan. Untuk Unicode sembarang, tentukan terlebih dahulu apakah pencocokan beroperasi pada code point atau user-perceived grapheme cluster.

• Bisakah salah satu string kosong? Batasan standar mengecualikan string kosong. Fungsi contoh mengembalikan string kosong untuk

t kosong, s kosong, atau s.length < t.length.

• Haruskah fungsi mengembalikan teks atau indeks? Masalah utama mengembalikan teks. Untuk indeks, kembalikan

[bestStart, bestStart + bestLength) tanpa mengubah pemindaian inti.

Pertanyaan-pertanyaan ini dapat mengubah predikat validitas, representasi indeks, atau aturan keluaran. Preferensi bahasa, nama variabel, dan implementasi hash-map spesifik tidak mengubah pilihan algoritma.

Kerangka Jawaban 30 Detik

"Saya akan menghitung frekuensi target di need dan mempertahankan sebuah jendela dengan dua pointer. Saat pointer kanan berekspansi, formed bertambah hanya ketika satu kelas karakter pertama kali mencapai kebutuhannya. Setelah setiap kelas terpenuhi, saya mencatat jawabannya dan memajukan pointer kiri hingga jendela menjadi tidak valid. Proses itu memeriksa jendela valid terpendek untuk setiap batas kanan. Kedua pointer hanya bergerak ke kanan, sehingga setiap posisi masuk dan keluar paling banyak satu kali: waktu O(|s| + |t|) dan ruang frequency-map O(u)."

Pembahasan Mendalam Langkah demi Langkah

Langkah 1: Gunakan baseline untuk mengungkap pekerjaan yang berulang.

Untuk setiap batas kiri, seseorang dapat memperluas batas kanan sambil mempertahankan frekuensi dan berhenti di jendela valid pertama. Hal ini menghindari penghitungan ulang setiap substring, tetapi masih dapat memindai ulang sebagian besar s dari setiap batas kiri, menghabiskan waktu O(|s|^2 + |t|). Menghitung ulang setiap substring dari awal bisa membutuhkan waktu kubik.

Di sini, u adalah jumlah karakter berbeda di t, paling banyak 52 di bawah batasan huruf alfabet Inggris. Desain state tetap menjadi bagian penting dari solusi linear; alfabet yang kecil tidak boleh menyembunyikan pengecekan validitas yang salah.

Langkah 2: Tentukan state yang cukup untuk pengecekan validitas berwaktu konstan.

need menyimpan frekuensi target. window menyimpan frekuensi karakter target di jendela saat ini. required = need.size adalah jumlah kelas karakter yang harus dipenuhi, dan formed adalah jumlah kelas yang telah mencapai frekuensi yang dibutuhkan. Jendela tersebut valid tepat ketika formed === required.

Pembaruan harus dikaitkan dengan perlintasan ambang batas kebutuhan:

after adding c: window[c] changes from need[c]-1 to need[c], so formed += 1
after adding c: window[c] changes from need[c] to need[c]+1, so formed is unchanged
before removing c: window[c] equals need[c], so removal causes formed -= 1
before removing c: window[c] exceeds need[c], so removal leaves formed unchanged

Memperlakukan formed sebagai hitungan mentah karakter target membuat salinan berlebih mudah terhitung berlebih. Menambahkan (increment) pada setiap karakter target tanpa membatasi kontribusinya akan salah menandai t = "AABC" sebagai tercakup terlalu dini.

Langkah 3: Tetapkan urutan ekspansi, pencatatan, dan kontraksi.

Pointer kanan memasukkan s[right] dan memperbarui state. Ketika jendela menjadi valid, loop dalam pertama-tama mempertimbangkan [left, right] untuk jawaban dan kemudian bersiap untuk menghapus s[left]. Jika penghapusan membuat satu kelas karakter menjadi kurang dari kebutuhan, kurangi (decrement) formed, kurangi frekuensinya, dan majukan left.

Mencatat sebelum menghapus mencegah kandidat yang valid terlewatkan. Menguji kesetaraan sebelum mengurangi frekuensi membuat transisi ambang batas menjadi eksplisit. Implementasi yang benar dapat mengurangi frekuensi terlebih dahulu dan menguji nilai di bawah kebutuhan, tetapi penjelasan dan kondisinya harus menggunakan urutan yang sama.

Langkah 4: Terapkan pemindaian linear.

export function minWindow(s: string, t: string): string {
  if (t.length === 0 || s.length < t.length) return "";

  const need = new Map<string, number>();
  for (const char of t) {
    need.set(char, (need.get(char) ?? 0) + 1);
  }

  const window = new Map<string, number>();
  const required = need.size;
  let formed = 0;
  let left = 0;
  let bestStart = 0;
  let bestLength = Number.POSITIVE_INFINITY;

  for (let right = 0; right < s.length; right += 1) {
    const char = s[right];
    const target = need.get(char);

    if (target !== undefined) {
      const nextCount = (window.get(char) ?? 0) + 1;
      window.set(char, nextCount);
      if (nextCount === target) formed += 1;
    }

    while (formed === required) {
      const length = right - left + 1;
      if (length < bestLength) {
        bestStart = left;
        bestLength = length;
      }

      const leftChar = s[left];
      const leftTarget = need.get(leftChar);
      if (leftTarget !== undefined) {
        const currentCount = window.get(leftChar) ?? 0;
        if (currentCount === leftTarget) formed -= 1;
        window.set(leftChar, currentCount - 1);
      }
      left += 1;
    }
  }

  return Number.isFinite(bestLength)
    ? s.slice(bestStart, bestStart + bestLength)
    : "";
}

Implementasi ini hanya menyimpan hitungan untuk karakter target. Karakter non-target tetap memengaruhi panjang jendela dan batas kirinya, sehingga tidak dapat dihapus dari s sebelumnya; karakter tersebut hanya tidak memerlukan entri di dalam frequency map.

Langkah 5: Nyatakan invarian dan buktikan kebenarannya.

Di akhir setiap iterasi loop luar, fakta-fakta berikut berlaku:

1. window[c] sama dengan hitungan sebenarnya dari karakter target c dalam interval saat ini [left, right].
2. formed sama persis dengan jumlah kelas target yang memenuhi window[c] >= need[c].
3. Setelah loop dalam berakhir, jendela saat ini tidak valid. Jendela valid terakhir yang baru saja diperiksa adalah jendela valid terpendek untuk

batas akhir right tersebut.

1. left hanya bergerak ke kanan. Setiap batas kiri sebelumnya yang sudah dilewati akan menghasilkan jendela yang lebih panjang untuk batas kanan yang sama,

dan memperluas batas kanan di kemudian hari tidak dapat membuatnya mengalahkan kandidat yang telah dipertimbangkan pada batas sebelumnya tersebut.

Jendela awal yang kosong memenuhi dua invarian pertama. Menambahkan karakter kanan memperbarui hitungan sebenarnya, dan aturan ambang batas mempertahankan invarian kedua. Selama jendela valid, algoritma mencatat kandidat sebelum setiap penghapusan, sehingga ia memeriksa semua batas kiri valid yang berakhir pada right saat ini hingga dua invarian pertama menyatakan jendela tersebut tidak valid. Berdasarkan induksi atas batas-batas kanan, algoritma memeriksa jendela valid terpendek untuk masing-masing batas kanan. Optimum global pasti berada di antara kandidat-kandidat tersebut, sehingga jawaban yang dicatat adalah benar.

Langkah 6: Telusuri target dengan karakter duplikat.

Misalkan s = "AAABBC" dan t = "AABC":

need = {A:2, B:1, C:1}, required = 3
right=0, A:1  formed=0
right=1, A:2  formed=1
right=2, A:3  formed=1    surplus A does not count twice
right=3, B:1  formed=2
right=4, B:2  formed=2    surplus B does not count twice
right=5, C:1  formed=3    [0,5] is valid
remove A at index 0: A:2, still valid; record [1,5] = "AABBC"
remove another A: A:1, formed falls to 2, so contraction stops

Penelusuran ini memeriksa tiga detail independen: frekuensi yang dibutuhkan lebih dari satu, tidak ada penghitungan ganda di atas kebutuhan, dan kontraksi yang berlanjut setelah menghapus salinan berlebih.

Langkah 7: Analisis kompleksitas secara akurat.

Membangun need memindai t satu kali. Pointer kanan memindai s satu kali, dan pointer kiri dapat bergerak dari 0 ke s.length hanya satu kali di sepanjang keseluruhan eksekusi. Oleh karena itu, kerja kumulatif dari loop dalam while adalah O(|s|). Dengan operasi map rata-rata O(1), total waktunya adalah O(|s| + |t|). Kedua frequency map menyimpan paling banyak u karakter target, sehingga ruang ekstranya adalah O(u); di bawah batasan huruf alfabet Inggris, u <= 52.

Langkah 8: Verifikasi dengan oracle dan properti.

Paling tidak, pengujian tetap harus mencakup:

("ADOBECODEBANC", "ABC") -> "BANC"   standard mixed input
("AAABBC", "AABC")       -> "AABBC"  duplicate requirement
("a", "a")               -> "a"      minimum size
("a", "A")               -> ""       case-sensitive and impossible
("abc", "abcd")          -> ""       s is shorter than t
("abc", "")              -> ""       defensive empty target

Untuk string acak pendek, bandingkan dengan oracle kuadratik yang mengenumerasi setiap interval. Periksa tiga properti dari hasil yang dioptimalkan: ia merupakan substring kontinu dari s, frekuensinya mencakup t, dan tidak ada interval yang lebih pendek yang mencakup t. Pengujian diferensial sangat efektif dalam mengungkap formed yang terhitung berlebih, panjang jawaban yang meleset satu (off-by-one), dan urutan penghapusan yang salah.

Ketika s sangat kecil, operasinya dilakukan sekali saja, dan performa tidak dibatasi, versi kuadratik lebih pendek dan mungkin lebih aman untuk ditulis di bawah tekanan wawancara. Dengan batas panjang 100000 dan target waktu linear yang eksplisit, sliding window adalah solusi akhir yang tepat.

Contoh Jawaban Berkualitas Tinggi

"Pertama-tama saya akan mengonfirmasi bahwa pencakupan didasarkan pada frekuensi karakter, urutan tidak berpengaruh, dan pencocokan bersifat case-sensitive. Baseline menetapkan setiap batas kiri dan berekspansi ke kanan, yang bernilai kuadratik pada kasus terburuk. Masalah ini memiliki monotonisitas yang berguna: menambahkan karakter kanan tidak dapat membatalkan jendela yang sudah valid, dan setelah jendela valid, memajukan batas kiri dapat menemukan jendela valid terpendek yang berakhir pada batas kanan tersebut.

Saya akan menyimpan frekuensi t di need dan frekuensi target saat ini di window. Saya juga akan mempertahankan formed, yaitu jumlah kelas karakter yang telah mencapai kebutuhannya. Menambahkan karakter meng-increment formed hanya ketika hitungannya menjadi tepat sama dengan hitungan yang dibutuhkan. Selama jendela valid, saya mencatatnya sebelum menghapus karakter kiri. Jika karakter tersebut tepat berada pada hitungan yang dibutuhkan sebelum dihapus, penghapusan membuatnya kurang dari kebutuhan, sehingga saya men-decrement formed.

Invarian utamanya adalah bahwa window cocok dengan hitungan sebenarnya di [left, right] dan bahwa formed cocok dengan jumlah kelas target yang terpenuhi. Loop dalam memeriksa setiap batas kiri yang valid untuk setiap batas kanan dan berhenti tepat setelah melewati yang terpendek yang valid. Optimum global berada di antara kandidat-kandidat tersebut. Kedua pointer hanya bergerak ke kanan, sehingga setiap posisi masuk dan keluar paling banyak satu kali. Waktunya adalah O(|s| + |t|) dan ruangnya adalah O(u). Saya akan menguji target dengan duplikat, tanpa solusi, input satu karakter, perbedaan huruf besar/kecil, dan string acak pendek terhadap brute-force oracle."

Kesalahan Umum

• Hanya menyimpan himpunan (set) karakter target → persyaratan duplikat hilang → simpan frekuensi yang dibutuhkan.
• Meng-increment hitungan kecocokan untuk setiap karakter target yang ditambahkan → salinan berlebih menciptakan validitas palsu → **increment formed

hanya pada transisi pertama ke hitungan yang dibutuhkan.**

• Selalu men-decrement formed saat menghapus karakter target → menghapus salinan berlebih membiarkan jendela tetap valid → **decrement

hanya ketika hitungan sebelum penghapusan sama dengan kebutuhan.**

• Mengontraksi hanya sekali setelah menjadi valid → jendela yang lebih pendek yang berakhir pada batas kanan yang sama terlewatkan → **gunakan loop while

hingga jendela pertama kali menjadi tidak valid.**

• Menggeser left sebelum mencatat jawaban → nilai minimum yang valid dapat terlewatkan atau terukur meleset satu → **ukur

[left, right] terlebih dahulu.**

• Memindai seluruh need setelah setiap pergeseran pointer → pengecekan validitas menambahkan faktor u → **pertahankan hitungan kelas yang terpenuhi

secara inkremental.**

• Menyelesaikan masalah subsequence → posisi di dalam hasil mungkin terlewati, sehingga jawaban tidak lagi kontinu → **representasikan

setiap jendela sebagai satu interval indeks kontinu.**

• Memfilter karakter non-target lalu memotong (slice) string asli dengan indeks hasil filter → posisi yang difilter tidak memetakan

secara langsung kembali ke sumbernya → pertahankan pointer pada string asli dan abaikan non-target hanya di dalam map.

• Menyebut loop dalam sebagai kuadratik → ini mengabaikan pointer kiri yang monoton secara global → **amortisasi atas setiap posisi yang keluar

paling banyak satu kali.**

• Hanya menguji contoh standar → duplikat, kasus yang tidak memungkinkan, dan case-sensitivity tetap tidak teruji → **tambahkan kasus uji adversarial

tetap dan random oracle.**

Pertanyaan Lanjutan dan Tanggapan

Pertanyaan lanjutan 1: Mengapa menghitung kelas karakter yang terpenuhi alih-alih total karakter yang cocok?

Kedua state tersebut dapat mendukung algoritma yang benar, tetapi penghitungan kelas membuat transisi ambang batas menjadi eksplisit. Untuk need[A] = 2, kelas menjadi terpenuhi hanya ketika window[A] bergerak dari 1 ke 2; kemunculan A ketiga tidak mengubah status tersebut. Penghapusan membatalkan status hanya ketika hitungan bergerak dari 2 ke 1. Penghitung total-karakter harus meng-increment hanya ketika window[c] <= need[c] dan menggunakan aturan penghapusan simetris, yang lebih rentan salah dinyatakan.

Pertanyaan lanjutan 2: Apa yang dapat disederhanakan jika t tidak memiliki karakter duplikat?

Setiap nilai di need adalah 1, sehingga window dapat direpresentasikan oleh hitungan karakter target atau oleh himpunan (set) yang dipasangkan dengan hitungan kemunculan. Salinan berulang dari target yang sama masih dapat muncul di dalam jendela, dan menghapus satu salinan mungkin tetap membiarkan kelas tersebut terpenuhi. Mempertahankan implementasi frekuensi umum hanya menambah sedikit overhead konstan dan secara langsung menangani masalah aslinya.

Pertanyaan lanjutan 3: Bagaimana jika karakter harus muncul sesuai urutan yang ditentukan oleh t?

Itu adalah Minimum Window Subsequence. Cakupan frekuensi tidak lagi membuktikan validitas: s = "cba" mencakup frekuensi dari t = "abc" tetapi memiliki urutan yang salah. Solusi dapat menggunakan pemrograman dinamis (dynamic programming) untuk mempertahankan posisi awal untuk setiap prefiks yang cocok, atau pemindaian maju dan mundur di sekitar batas akhir kandidat. Kompleksitasnya memerlukan analisis baru, dan formed === required tidak dapat digunakan kembali sebagai kondisi validitas.

Pertanyaan lanjutan 4: Bagaimana cara Anda mengembalikan semua jendela terpendek yang memiliki panjang sama?

Tanpa jaminan keunikan, pertahankan bestLength seperti sebelumnya. Ketika jendela yang lebih pendek muncul, kosongkan daftar hasil dan tambahkan interval tersebut. Ketika jendela dengan panjang yang sama muncul, tambahkan ke daftar. Jika jalur pencarian terpisah dapat menemukan kembali interval teks yang sama, lakukan deduplikasi berdasarkan [left, right]; penelusuran dua pointer ini mengunjungi setiap interval paling banyak satu kali, sehingga tidak diperlukan himpunan (set) ekstra di sini.

Pertanyaan lanjutan 5: Bagaimana jika s berupa aliran karakter (stream) yang tidak muat dalam memori?

Frekuensi yang dibutuhkan dan state pointer masih dapat diperbarui secara online, tetapi mengembalikan teks asli memerlukan penyimpanan interval kandidat saat ini. Sebuah antrean (queue) dapat menyimpan karakter dari left hingga posisi terbaru beserta offset global. Jika tidak ada jendela valid yang muncul dalam waktu lama, buffer tersebut dapat mendekati seluruh aliran yang telah dibaca sejauh ini. Mengembalikan panjang dan offset saja memungkinkan lebih banyak kompresi di sekitar posisi karakter target; mengembalikan teks memerlukan kebijakan ukuran jendela maksimum (maximum-window) atau penyimpanan eksternal yang eksplisit.

Pertanyaan lanjutan 6: Bagaimana Anda mendukung teks Unicode sembarang?

Pertama-tama tentukan unit pencocokannya. Untuk code point Unicode, lakukan iterasi berdasarkan code point dan pertahankan offset unit kode UTF-16 yang sesuai untuk memotong (slice) string JavaScript asli. Karakter yang dirasakan pengguna (user-perceived character) dapat memuat beberapa code point; mencocokkan grapheme cluster memerlukan segmenter yang andal. Normalisasi juga mengubah definisi kesetaraan karakter, sehingga harus diterapkan secara konsisten sebelum penghitungan sembari mempertahankan pemetaan ke teks sumber.

Pertanyaan lanjutan 7: Bagaimana Anda bisa memercayai test oracle yang diacak?

Oracle hanya berjalan pada string pendek, sehingga ia dapat mengenumerasi setiap [left, right], menghitung ulang setiap interval secara langsung, dan memilih berdasarkan panjang serta posisi awal. Alur kontrolnya sengaja dibuat berbeda dari algoritma yang dioptimalkan, menjadikannya lambat tetapi mudah diaudit. Validasi oracle pada contoh tetap terlebih dahulu, kemudian bandingkan panjang hasil, kontinuitas, dan cakupan frekuensi selama pengujian diferensial acak untuk mengurangi kemungkinan adanya bug yang sama.