Temu Duga Pengekodan: Bagaimana Anda Menyelesaikan Minimum Window Substring?

Masalah dan Bila Ia Digunakan

Diberi rentetan s dan t, cari subrentetan bersebelahan terpendek bagi s yang mengandungi setiap aksara daripada t sekurang-kurangnya sebanyak mana ia muncul dalam t. Pemadanan adalah sensitif huruf besar/kecil (case-sensitive). Sebagai contoh:

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

Jika t = "AABC", tetingkap calon memerlukan sekurang-kurangnya dua aksara A, satu B, dan satu C. Semakan keahlian set kehilangan keperluan kemunculan berganda (multiplicity) ini, yang merupakan kesilapan semantik paling biasa dalam masalah ini.

Kekangannya ialah 1 <= s.length, t.length <= 100000, dan kedua-dua rentetan hanya mengandungi huruf Bahasa Inggeris huruf besar dan huruf kecil. Jika jawapan wujud, jawapan terpendek adalah unik. Kembalikan rentetan kosong apabila tiada tetingkap meliputi t. Pelaksanaan di bawah juga mengendalikan t kosong dan s lebih pendek daripada t secara defensif, walaupun input tersebut berada di luar kekangan standard.

Rekod temu duga kejuruteraan perisian awam baru-baru ini masih menunjukkan Minimum Window Substring, termasuk variasi di mana t tidak mempunyai aksara pendua. Platform pengekodan Bahasa Inggeris dan Bahasa Cina juga mengekalkan masalah ini. Kemahiran terasnya ialah menukar carian selang minimum global menjadi keadaan yang dikekalkan secara berperingkat (incrementally), jadi kategori yang tepat ialah coding; bahasa contoh tidak mengubah klasifikasi tersebut.

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah pemodelan yang tepat. Jawapan yang kukuh menyatakan "mengandungi t" sebagai kekangan kekerapan: untuk setiap aksara sasaran c, tetingkap semasa mesti memenuhi window[c] >= need[c]. Sekadar mengatakan bahawa semua aksara sasaran telah muncul tidak dapat mengendalikan t = "AA".

Isyarat kedua ialah mengenali kemonotonan di sebalik garis dasar kuadratik. Menggerakkan sempadan kanan hanya menambah aksara, jadi tetingkap yang sah kekal sah apabila diperluas. Untuk sempadan kanan yang tetap, menggerakkan sempadan kiri membuang aksara. Sebaik sahaja tetingkap adalah sah, ia boleh dikecutkan sehingga ia baru sahaja menjadi tidak sah, merekodkan calon yang lebih pendek sepanjang proses tersebut.

Isyarat ketiga ialah memampatkan semakan kesahan. Mengimbas keseluruhan jadual kekerapan pada setiap pergerakan menghilangkan batas linear. Pelaksanaan ini menggunakan formed untuk bilangan kelas aksara sasaran yang kekerapan diperlukannya telah dicapai, dengan required = need.size. formed meningkat apabila kekerapan mula-mula menyamai keperluannya dan menurun apabila penyingkiran menjadikannya di bawah keperluan tersebut. Salinan lebihan tidak dikira dua kali.

Akhir sekali, calon harus mewajarkan ketepatan dan sempadan: mengapa tetingkap sah terpendek bagi setiap sempadan kanan diperiksa, mengapa titik akhir kiri yang dibuang tidak dapat menghasilkan calon masa depan yang lebih baik, dan mengapa setiap penunjuk bergerak paling banyak s.length kali.

Soalan untuk Dijelaskan Sebelum Menjawab

• Adakah pemadanan sensitif huruf besar/kecil? Ya, untuk masalah ini. Jika pemadanan harus mengabaikan huruf besar/kecil, tentukan penormalan terlebih dahulu; penormalan boleh mengubah

pemetaan kembali kepada indeks dalam rentetan asal.

• Adakah "mengandungi" mengekalkan susunan daripada t? Tidak. Masalah ini hanya memerlukan liputan kekerapan. Memerlukan susunan menghasilkan

masalah Minimum Window Subsequence, di mana syarat kesahan ini tidak berfungsi.

• Adakah aksara sasaran pendua dikira secara berasingan? Ya. t = "AABC" memerlukan dua aksara A, secara langsung mendorong penggunaan

peta kekerapan.

• Apakah yang berlaku apabila beberapa tetingkap terpendek terikat sama panjang? Masalah standard menjamin keunikan. Tanpa jaminan itu, pelaksanaan

ini mengembalikan tetingkap terpendek yang terawal kerana ia hanya mengemas kini pada panjang yang lebih kecil secara ketat.

• Apakah set aksaranya? Input adalah huruf Bahasa Inggeris, jadi pengindeksan unit kod UTF-16 JavaScript tidak boleh memisahkan aksara

yang dibenarkan. Untuk Unicode sewenang-wenangnya, tentukan dahulu sama ada pemadanan beroperasi pada titik kod (code points) atau kluster grafem yang dilihat pengguna.

• Bolehkah mana-mana rentetan kosong? Kekangan standard mengecualikan rentetan kosong. Fungsi sampel mengembalikan rentetan kosong untuk

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

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

[bestStart, bestStart + bestLength) tanpa mengubah imbasan teras.

Soalan-soalan ini boleh mengubah predikat kesahan, perwakilan indeks, atau peraturan output. Pilihan bahasa, nama pemboleh ubah, dan pelaksanaan peta cincang tertentu tidak mengubah pilihan algoritma.

Rangka Jawapan 30-Saat

"Saya akan mengira kekerapan sasaran dalam need dan mengekalkan tetingkap dengan dua penunjuk. Semasa penunjuk kanan mengembang, formed meningkat hanya apabila satu kelas aksara mula-mula mencapai keperluannya. Sebaik sahaja setiap kelas dipenuhi, saya merekodkan jawapan dan memajukan penunjuk kiri sehingga tetingkap menjadi tidak sah. Itu memeriksa tetingkap sah terpendek bagi setiap titik akhir kanan. Kedua-dua penunjuk bergerak hanya ke kanan, jadi setiap kedudukan masuk dan keluar paling banyak sekali: masa O(|s| + |t|) dan ruang peta kekerapan O(u)."

Perbincangan Mendalam Langkah Demi Langkah

Langkah 1: Gunakan garis dasar untuk mendedahkan kerja yang berulang.

Bagi setiap titik akhir kiri, seseorang boleh memanjangkan titik akhir kanan sambil mengekalkan kekerapan dan berhenti pada tetingkap sah pertama. Ini mengelakkan pengiraan semula setiap subrentetan, tetapi ia masih boleh mengimbas semula sebahagian besar daripada s daripada setiap titik akhir kiri, mengambil masa O(|s|^2 + |t|). Mengira semula setiap subrentetan dari awal boleh menjadi kubik.

Di sini, u ialah bilangan aksara berbeza dalam t, paling banyak 52 di bawah kekangan huruf Bahasa Inggeris. Reka bentuk keadaan kekal sebagai bahagian penting dalam penyelesaian linear; abjad yang kecil tidak sepatutnya menyembunyikan semakan kesahan yang tidak betul.

Langkah 2: Tentukan keadaan yang mencukupi untuk semakan kesahan masa malar.

need menyimpan kekerapan sasaran. window menyimpan kekerapan aksara sasaran dalam tetingkap semasa. required = need.size ialah bilangan kelas aksara yang perlu dipenuhi, dan formed ialah bilangan yang telah mencapai kekerapan yang diperlukan. Tetingkap adalah sah tepat apabila formed === required.

Kemas kini mesti terikat dengan melintasi ambang keperluan:

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 kiraan mentah aksara sasaran menjadikan salinan lebihan mudah terlebih kira. Menambah pada setiap aksara sasaran tanpa mengehadkan sumbangan akan menandakan t = "AABC" sebagai diliputi terlalu awal secara salah.

Langkah 3: Tetapkan susunan peluasan, perekodan, dan pengecutan.

Penunjuk kanan memasukkan s[right] dan mengemas kini keadaan. Apabila tetingkap menjadi sah, gelung dalam mula-mula mempertimbangkan [left, right] untuk jawapan dan kemudian bersedia untuk membuang s[left]. Jika penyingkiran menjadikan satu kelas aksara berkurangan, kurangkan formed, kurangkan kekerapan, dan majukan left.

Merekod sebelum penyingkiran menghalang calon yang sah daripada terlepas. Menguji kesaksamaan sebelum mengurangkan kekerapan menjadikan peralihan ambang jelas. Pelaksanaan yang betul boleh mengurangkan terlebih dahulu dan menguji nilai di bawah keperluan, tetapi penjelasan dan syarat mesti menggunakan susunan yang sama.

Langkah 4: Laksanakan imbasan 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)
    : "";
}

Pelaksanaan ini menyimpan kiraan hanya untuk aksara sasaran. Aksara bukan sasaran masih mempengaruhi panjang tetingkap dan sempadan kirinya, jadi ia tidak boleh dipadamkan daripada s lebih awal; ia cuma tidak memerlukan entri dalam peta kekerapan.

Langkah 5: Nyatakan invarian dan buktikan ketepatan.

Pada akhir setiap lelaran gelung luar, fakta berikut adalah benar:

1. window[c] menyamai kiraan sebenar aksara sasaran c dalam selang semasa [left, right].
2. formed menyamai tepat bilangan kelas sasaran yang memenuhi window[c] >= need[c].
3. Selepas gelung dalam berakhir, tetingkap semasa adalah tidak sah. Tetingkap sah terakhir yang baru diperiksa ialah tetingkap sah terpendek bagi

titik akhir right tersebut.

1. left bergerak hanya ke arah kanan. Sebarang titik akhir kiri terdahulu yang telah dilalui akan mencipta tetingkap yang lebih panjang untuk titik akhir kanan yang sama,

dan memanjangkan titik akhir kanan kemudiannya tidak boleh menjadikannya mengalahkan calon yang telah dipertimbangkan pada titik akhir terdahulu tersebut.

Tetingkap awal yang kosong memenuhi dua invarian pertama. Menambah aksara kanan mengemas kini kiraan sebenar, dan peraturan ambang mengekalkan invarian kedua. Semasa tetingkap adalah sah, algoritma merekodkan calon sebelum setiap penyingkiran, jadi ia memeriksa semua sempadan kiri yang sah yang berakhir pada right semasa sehingga dua invarian pertama menyatakan tetingkap tidak sah. Secara aruhan ke atas titik akhir kanan, algoritma memeriksa tetingkap sah terpendek bagi setiap satu. Optimum global mesti berada dalam kalangan calon-calon tersebut, jadi jawapan yang direkodkan adalah betul.

Langkah 6: Jejak sasaran dengan aksara pendua.

Biarkan 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

Jejakan ini menyemak tiga butiran bebas: kekerapan yang diperlukan melebihi satu, tiada pengiraan dua kali di atas keperluan, dan pengecutan berterusan selepas membuang salinan lebihan.

Langkah 7: Analisis kerumitan dengan tepat.

Membina need mengimbas t sekali. Penunjuk kanan mengimbas s sekali, dan penunjuk kiri boleh bergerak dari 0 ke s.length hanya sekali sepanjang keseluruhan pelaksanaan. Kerja kumulatif gelung while dalam oleh itu ialah O(|s|). Dengan purata operasi peta O(1), jumlah masa ialah O(|s| + |t|). Dua peta kekerapan menyimpan paling banyak u aksara sasaran, jadi ruang tambahan ialah O(u); di bawah kekangan huruf Bahasa Inggeris, u <= 52.

Langkah 8: Sahkan dengan orakel dan sifat.

Sekurang-kurangnya, ujian tetap harus merangkumi:

("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 rentetan rawak pendek, bandingkan dengan orakel kuadratik yang menyenaraikan setiap selang. Semak tiga sifat hasil yang dioptimumkan: ia adalah subrentetan bersebelahan bagi s, kekerapannya meliputi t, dan tiada selang yang lebih pendek meliputi t. Ujian pembezaan (differential testing) amat berkesan untuk mendedahkan formed yang terlebih kira, ralat panjang jawapan off-by-one, dan susunan penyingkiran yang tidak betul.

Apabila s adalah sangat kecil, operasi adalah sekali sahaja, dan prestasi tidak dikekang, versi kuadratik adalah lebih pendek dan mungkin lebih selamat untuk ditulis di bawah tekanan temu duga. Dengan batas panjang 100000 dan sasaran masa linear yang jelas, tetingkap gelongsor adalah penyelesaian akhir yang sesuai.

Sampel Jawapan Berkualiti Tinggi

"Saya mula-mula akan mengesahkan bahawa liputan adalah berdasarkan kekerapan aksara, susunan tidak penting, dan pemadanan adalah sensitif huruf besar/kecil. Garis dasar menetapkan setiap titik akhir kiri dan mengembang ke kanan, yang merupakan kuadratik dalam kes terburuk. Masalah ini mempunyai kemonotonan yang berguna: menambah aksara kanan tidak boleh membatalkan tetingkap yang sah, dan sebaik sahaja tetingkap adalah sah, memajukan titik akhir kiri boleh mencari tetingkap sah terpendek yang berakhir pada titik akhir kanan tersebut.

Saya akan menyimpan kekerapan t dalam need dan kekerapan sasaran semasa dalam window. Saya juga akan mengekalkan formed, bilangan kelas aksara yang telah mencapai keperluan mereka. Menambah aksara meningkatkan formed hanya apabila kiraannya menjadi tepat kiraan yang diperlukan. Semasa tetingkap adalah sah, saya merekodkannya sebelum membuang aksara kiri. Jika aksara itu tepat pada kiraan yang diperlukannya sebelum penyingkiran, penyingkiran tersebut menjadikan kelas itu berkurangan, jadi saya mengurangkan formed.

Invarian utama ialah window sepadan dengan kiraan sebenar dalam [left, right] dan formed sepadan dengan bilangan kelas sasaran yang dipenuhi. Gelung dalam menyemak setiap sempadan kiri yang sah untuk setiap titik akhir kanan dan berhenti sejurus selepas melepasi yang terpendek yang sah. Optimum global adalah antara calon-calon tersebut. Kedua-dua penunjuk bergerak hanya ke kanan, jadi setiap kedudukan masuk dan keluar paling banyak sekali. Masanya ialah O(|s| + |t|) dan ruang ialah O(u). Saya akan menguji sasaran pendua, tiada penyelesaian, input satu aksara, perbezaan huruf besar/kecil, dan rentetan pendek rawak terhadap orakel tenaga kasar."

Kesilapan Biasa

• Menyimpan hanya set aksara sasaran → keperluan pendua hilang → simpan kekerapan yang diperlukan.
• Meningkatkan kiraan padanan untuk setiap aksara sasaran yang ditambah → salinan lebihan mencipta kesahan palsu → **tingkatkan formed

hanya pada peralihan pertama kepada kiraan yang diperlukan.**

• Sentiasa mengurangkan formed apabila membuang aksara sasaran → membuang salinan lebihan mengekalkan tetingkap sah → **kurangkan

hanya apabila kiraan pra-penyingkiran menyamai keperluan.**

• Mengecut hanya sekali selepas menjadi sah → tetingkap lebih pendek yang berakhir pada sempadan kanan yang sama dilangkau → **gunakan gelung while

sehingga tetingkap mula-mula menjadi tidak sah.**

• Menggerakkan left sebelum merekodkan jawapan → minimum yang sah boleh dilangkau atau diukur ralat satu (off by one) → **ukur

[left, right] terlebih dahulu.**

• Mengimbas semua need selepas setiap pergerakan penunjuk → semakan kesahan menambah faktor u → **kekalkan kiraan kelas yang dipenuhi

secara berperingkat.**

• Menyelesaikan masalah suburutan (subsequence) → kedudukan di dalam hasil mungkin dilangkau, jadi jawapan tidak lagi bersebelahan → **wakili

setiap tetingkap sebagai satu selang indeks yang berterusan.**

• Menapis aksara bukan sasaran dan kemudian memotong rentetan asal dengan indeks yang ditapis → kedudukan yang ditapis tidak memeta

secara langsung kembali kepada sumber → kekalkan penunjuk pada rentetan asal dan abaikan bukan sasaran hanya dalam peta.

• Memanggil gelung dalam sebagai kuadratik → ini mengabaikan penunjuk kiri yang monoton secara global → **dilunaskan (amortized) ke atas setiap kedudukan yang keluar paling

banyak sekali.**

• Menguji contoh standard sahaja → pendua, kes mustahil, dan kepekaan huruf besar/kecil kekal tidak diuji → **tambah kes lawan (adversarial) tetap

dan orakel rawak.**

Soalan Susulan dan Maklum Balas

Susulan 1: Mengapa mengira kelas aksara yang dipenuhi dan bukannya jumlah aksara yang dipadankan?

Mana-mana keadaan boleh menyokong algoritma yang betul, tetapi pengiraan kelas menjadikan peralihan ambang jelas. Untuk need[A] = 2, kelas menjadi dipenuhi hanya apabila window[A] beralih dari 1 ke 2; A ketiga tidak mengubah status itu. Penyingkiran membatalkan status tersebut hanya apabila kiraan beralih dari 2 ke 1. Pembilang jumlah aksara mesti bertambah hanya semasa window[c] <= need[c] dan menggunakan peraturan penyingkiran yang simetri, yang lebih mudah tersilap dinyatakan.

Susulan 2: Apakah yang boleh dipermudahkan jika t tidak mempunyai aksara pendua?

Setiap nilai dalam need ialah 1, jadi window boleh diwakili oleh kiraan aksara sasaran atau oleh set yang dipadankan dengan kiraan kejadian. Salinan berulang sasaran yang sama masih boleh muncul dalam tetingkap, dan membuang satu salinan mungkin membiarkan kelas itu dipenuhi. Mengekalkan pelaksanaan kekerapan umum menambah sedikit overhed malar dan secara langsung mengendalikan masalah asal.

Susulan 3: Bagaimana jika aksara mesti muncul dalam susunan yang ditentukan oleh t?

Itu ialah Minimum Window Subsequence. Liputan kekerapan tidak lagi membuktikan kesahan: s = "cba" meliputi kekerapan t = "abc" tetapi mempunyai susunan yang salah. Penyelesaian boleh menggunakan pengaturcaraan dinamik untuk mengekalkan kedudukan mula bagi setiap awalan yang dipadankan, atau imbasan ke hadapan dan ke belakang di sekitar titik akhir calon. Kerumitannya memerlukan analisis baharu, dan formed === required tidak boleh digunakan semula sebagai syarat kesahan.

Susulan 4: Bagaimanakah anda akan mengembalikan setiap tetingkap terpendek yang terikat sama panjang?

Tanpa jaminan keunikan, kekalkan bestLength seperti sebelum ini. Apabila tetingkap yang lebih pendek muncul, kosongkan senarai hasil dan tambah selang tersebut. Apabila tetingkap dengan panjang yang sama muncul, tambahkan padanya. Jika laluan carian berasingan boleh menemui semula selang teks yang sama, nyahduplikasi mengikut [left, right]; lintasan dua penunjuk ini melawat setiap selang paling banyak sekali, jadi tiada set tambahan diperlukan di sini.

Susulan 5: Bagaimana jika s ialah strim aksara yang tidak muat dalam memori?

Kekerapan yang diperlukan dan keadaan penunjuk masih boleh dikemas kini secara dalam talian (online), tetapi mengembalikan teks asal memerlukan pengekalan selang calon semasa. Baris gilir (queue) boleh menyimpan aksara daripada left melalui kedudukan terbaharu dengan ofset global. Jika tiada tetingkap yang sah muncul untuk masa yang lama, penimbal itu boleh menghampiri keseluruhan strim yang dibaca setakat ini. Mengembalikan panjang dan ofset sahaja membolehkan lebih banyak pemampatan di sekitar kedudukan aksara sasaran; mengembalikan teks memerlukan dasar tetingkap maksimum atau storan luaran yang jelas.

Susulan 6: Bagaimanakah anda akan menyokong teks Unicode sewenang-wenangnya?

Mula-mula tentukan unit pemadanan. Untuk titik kod Unicode, lelar mengikut titik kod dan kekalkan ofset unit kod UTF-16 yang sepadan untuk memotong rentetan JavaScript asal. Aksara yang dilihat pengguna mungkin mengandungi beberapa titik kod; pemadanan kluster grafem memerlukan pemecah segmen yang boleh dipercayai. Penormalan juga mengubah definisi kesaksamaan aksara, jadi ia mesti digunakan secara konsisten sebelum mengira sambil mengekalkan pemetaan kepada teks sumber.

Susulan 7: Bagaimanakah anda boleh mempercayai orakel ujian rawak?

Orakel hanya berjalan pada rentetan pendek, jadi ia boleh menyenaraikan setiap [left, right], mengira semula setiap selang secara langsung, dan memilih mengikut panjang dan kedudukan mula. Aliran kawalannya sengaja dibuat berbeza daripada algoritma yang dioptimumkan, menjadikannya perlahan tetapi mudah untuk diaudit. Sahkan orakel pada contoh tetap terlebih dahulu, kemudian bandingkan panjang hasil, ketersambungan (contiguity), dan liputan kekerapan semasa ujian pembezaan rawak untuk mengurangkan kemungkinan pepijat kongsi.