Minimum Window Substring

Q: Berapa kompleksitas waktu Minimum Window Substring?

Jendela penghitung yang hilang berjalan dalam waktu O(n + m) , dengan n dan m sebagai panjang s dan t . Pembuatan tabel membaca t satu kali, dan setiap karakter s masuk dan keluar dari jendela paling banyak satu kali. Memori tambahan yang digunakan adalah satu hitungan untuk setiap kode karakter.

Q: Apa perbedaan Minimum Window Substring dengan mencari anagram dalam sebuah string?

Anagram memiliki huruf yang sama persis dengan t , sehingga jendelanya memiliki panjang tetap m dan bergeser satu langkah setiap kali. Di sini, karakter tambahan diperbolehkan, jadi panjangnya menjadi bagian dari jawaban: jendela membesar sampai mencakup t , lalu mengecil selama masih mencakupnya.

SulitSliding window Hashing

+10

Kamu mendapatkan dua string, s dan t. Temukan substring terpendek dari s yang berisi setiap karakter dari t, termasuk karakter yang berulang: jika t berisi sebuah huruf dua kali, substring tersebut harus berisi huruf itu setidaknya dua kali. Urutannya tidak penting, dan karakter lain juga boleh muncul.

Jika ada beberapa substring terpendek, kembalikan yang paling kiri. Jika tidak ada substring yang berisi semua karakter dari t, kembalikan string kosong.

Fungsi

minWindow(s: string, t: string) → string

sstring: string yang akan dicari
tstring: karakter yang harus ada di jendela, termasuk karakter yang berulang
Mengembalikanstring: substring terpendek, lalu yang paling kiri, dari s yang memuat semua t, atau string kosong

Batasan

1 ≤ s.length ≤ 5 × 10⁴
1 ≤ t.length ≤ 10⁴
s dan t hanya berisi huruf bahasa Inggris. Huruf besar dan huruf kecil adalah karakter yang berbeda.
Jika ada beberapa substring yang paling pendek, jawabannya adalah yang paling kiri; jika tidak ada, jawabannya adalah "".

Contoh

Input: s = "mappingtheplan"t = "nap"
Output: "plan"
Penjelasan: Jendela pertama dari kiri yang memuat n, a, dan p adalah appin, lima karakter. plan memuat ketiganya dalam empat karakter, dan tidak ada rangkaian tiga karakter yang memuat semuanya.

Input: s = "banana"t = "aan"
Output: "ana"
Penjelasan: t membutuhkan dua salinan a dan satu n. ana pada indeks 1 memiliki tepat itu. ana kedua dimulai pada indeks 3, dan yang paling kiri yang dipilih.

Input: s = "Coddy"t = "cd"
Output: ""
Penjelasan: Huruf C dalam Coddy adalah huruf besar, karakter yang berbeda dari c. Tidak ada substring yang memuat huruf kecil c, jadi jawabannya adalah string kosong.

Pertanyaan lanjutan

Ketika t memakai sedikit huruf dan s panjang, sebagian besar s tidak pernah berpengaruh. Bisakah kamu membuat jendela melompat hanya di antara posisi yang berisi huruf dari t?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Yang penting hanya jumlah karakter dalam jendela, bukan urutannya. Geser tepi kanan hingga jendela mencakup t, lalu geser tepi kiri selama jendela masih mencakupnya. Kedua tepi tidak pernah bergerak mundur. Penghitung karakter yang belum terpenuhi memberi tahu kamu dalam satu langkah apakah jendela mencakup t.

Besarkan jendela dari setiap titik awal

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Tetapkan posisi awal dan perbesar jendela satu karakter setiap kali, sambil menghitung setiap karakter. Setelah setiap langkah, periksa setiap huruf u yang digunakan t. Ujung pertama yang memenuhi syarat menghasilkan jendela terpendek yang mencakup semua huruf dari posisi awal ini, jadi berhentilah di sana. Posisi awal diperiksa dari kiri ke kanan dan hanya jendela yang benar-benar lebih pendek yang menggantikan jendela terbaik, jadi jika panjangnya sama, yang paling kiri tetap dipilih.

Jika tidak ada jendela yang memenuhi syarat, setiap posisi awal akan membaca hingga akhir s: sekitar n²/2 langkah, 1.25 × 10^9 untuk n = 5 × 10^4.

Algoritma

Hitung jumlah kemunculan setiap huruf yang diminta t.
Untuk setiap start, kosongkan tabel hitungan lalu geser end ke kanan sambil menambahkan s[end].
Saat window memuat cukup banyak setiap huruf, simpan jika panjangnya benar-benar lebih pendek daripada yang terbaik, lalu lanjutkan ke start berikutnya.
Kembalikan window terbaik, atau "" jika tidak ada yang mencakup t.

def minWindow(s, t):
    need = [0] * 128  # copies of each character code that t asks for
    for ch in t:
        need[ord(ch)] += 1
    letters = [c for c in range(128) if need[c] > 0]
    best_start, best_len = 0, len(s) + 1
    for start in range(len(s)):
        have = [0] * 128  # counts inside s[start..end]
        for end in range(start, len(s)):
            have[ord(s[end])] += 1
            if all(have[c] >= need[c] for c in letters):
                # The first end that covers t gives the shortest window from this start.
                if end - start + 1 < best_len:
                    best_start, best_len = start, end - start + 1
                break
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Menggeser jendela untuk memeriksa setiap huruf

Intuisi

Menambahkan karakter ke window yang mencakup target membuatnya tetap mencakup target, dan menghapus karakter dari window yang tidak mencakup sesuatu membuatnya tetap tidak mencakupnya. Jadi saat titik awal bergerak ke kanan, titik akhir window terpendek yang mencakup target tidak pernah bergerak ke kiri.

Tidak ada window yang terlewat. Ambil window terbaik, dari L hingga R. Agar left melewati L sebelum right mencapai R, window yang lebih pendek dari L harus mencakup t. Jadi saat right mencapai R, proses penyusutan menggerakkan left ke L dan mencatatnya.

Setiap ujung bergerak paling banyak n kali, tetapi setiap pemeriksaan membaca hingga u hitungan: O(n·u).

Algoritma

Hitung jumlah kemunculan yang diminta t; tetapkan left = 0 dan panjang terbaik ke n+1.
Untuk setiap right, tambahkan s[right] ke hitungan dalam jendela.
Selama setiap huruf dalam t memiliki jumlah yang cukup, catat jendela jika panjangnya lebih pendek, hapus s[left], lalu majukan left.
Kembalikan jendela terbaik, atau "" jika panjang terbaik masih n+1.

def minWindow(s, t):
    need = [0] * 128  # copies of each character code that t asks for
    for ch in t:
        need[ord(ch)] += 1
    letters = [c for c in range(128) if need[c] > 0]
    have = [0] * 128  # counts inside s[left..right]

    def covers():
        for c in letters:
            if have[c] < need[c]:
                return False
        return True

    left = 0
    best_start, best_len = 0, len(s) + 1
    for right in range(len(s)):
        have[ord(s[right])] += 1  # expand on the right
        while covers():  # shrink from the left while the window still covers t
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            have[ord(s[left])] -= 1
            left += 1
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Jendela geser dengan penghitung yang hilang

Intuisi

Ganti pemindaian dengan satu angka. Misalkan need[c] adalah jumlah kemunculan c yang diminta oleh t, dikurangi jumlah kemunculannya di dalam jendela; nilai negatif berarti ada kelebihan. Misalkan missing adalah jumlah kemunculan yang masih kurang di dalam jendela, dimulai dari panjang t. Jendela mencakup t dengan tepat saat missing bernilai 0.

Karakter yang masuk saat need-nya lebih dari 0 mengisi kekurangan, sehingga missing berkurang. Karakter yang penghapusannya membuat need lebih dari 0 menimbulkan kekurangan, sehingga missing bertambah. Kelebihan tidak memengaruhinya. Pada banana dengan t = aan, missing pertama kali mencapai 0 pada bana, dan menghapus b yang berlebih menyisakan ana yang tetap mencakup t.

Setiap karakter masuk dan keluar sekali dengan biaya tetap: waktu O(n + m), dengan satu tabel berisi 128 hitungan.

Algoritma

Isi need dengan jumlah t; atur missing ke panjang t, left = 0, dan panjang terbaik ke n+1.
Untuk setiap right: jika need[s[right]] lebih dari 0, kurangi missing; lalu kurangi need[s[right]].
Selama missing bernilai 0, catat jendela jika panjangnya benar-benar lebih pendek. Tambah need[s[left]]; jika sekarang lebih dari 0, tambah missing. Majukan left.
Kembalikan jendela terbaik, atau "" jika panjang terbaik masih n+1.

def minWindow(s, t):
    # need[c]: copies of c that t asks for minus copies inside the window.
    # Positive means the window still lacks c; negative means it holds spares.
    need = [0] * 128
    for ch in t:
        need[ord(ch)] += 1
    missing = len(t)  # characters of t the window does not cover yet
    left = 0
    best_start, best_len = 0, len(s) + 1
    for right in range(len(s)):
        c = ord(s[right])
        if need[c] > 0:  # this copy fills a gap
            missing -= 1
        need[c] -= 1
        while missing == 0:  # the window covers t: record it, then shrink
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            c = ord(s[left])
            need[c] += 1
            if need[c] > 0:  # gave away a copy t needs
                missing += 1
            left += 1
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Jebakan dan kasus tepi

Menghitung huruf, bukan jumlah kemunculannya. t = aan membutuhkan dua a, jadi ban tidak mencukupinya.
Mengubah missing untuk setiap karakter yang masuk atau keluar. a berlebih kemudian ikut dihitung, dan missing bisa mencapai 0 saat window tidak memiliki n.
Mengganti window terbaik saat panjangnya sama. Dalam contoh kedua, cara ini mengembalikan ana pada indeks 3.
Menggunakan n sebagai panjang untuk "tidak ditemukan". Saat jawabannya adalah seluruh s, panjangnya juga n; mulai dari n+1.
Menggunakan tabel dengan 26 slot yang diindeks berdasarkan c - 'a'. Huruf kapital, seperti pada contoh ketiga, berada di luar tabel.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Minimum Window Substring?

Jendela penghitung yang hilang berjalan dalam waktu O(n + m), dengan n dan m sebagai panjang s dan t. Pembuatan tabel membaca t satu kali, dan setiap karakter s masuk dan keluar dari jendela paling banyak satu kali. Memori tambahan yang digunakan adalah satu hitungan untuk setiap kode karakter.

Mengapa tepi kiri tidak pernah bergerak kembali?

Tepi kiri melewati suatu posisi hanya setelah jendela yang dimulai di sana mencakup t, dan jendela itu adalah yang paling pendek dari posisi awal tersebut. Setiap jendela dari sana yang berakhir lebih jauh akan lebih panjang, jadi kembali ke posisi sebelumnya tidak akan pernah menghasilkan jawaban yang lebih baik.

Apa perbedaan Minimum Window Substring dengan mencari anagram dalam sebuah string?

Anagram memiliki huruf yang sama persis dengan t, sehingga jendelanya memiliki panjang tetap m dan bergeser satu langkah setiap kali. Di sini, karakter tambahan diperbolehkan, jadi panjangnya menjadi bagian dari jawaban: jendela membesar sampai mencakup t, lalu mengecil selama masih mencakupnya.

def minWindow(s, t):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "mappingtheplan"
t = "nap"

Output yang diharapkan

"plan"

Minimum Window Substring

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Besarkan jendela dari setiap titik awal

Menggeser jendela untuk memeriksa setiap huruf

Jendela geser dengan penghitung yang hilang

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa