Link Soal : https://leetcode.com/problems/minimum-window-substring/

Permasalahan

Diberikan dua buah string s dan t dengan panjang masing-masing m dan n. Buat program yang mengembalikan window minimum dari s yang mengandung setiap karakter dari t (termasuk yang duplikat) di dalam window tersebut. Jika tidak ada yang memenuhi syarat, yang dikembalikan adalah string kosong "".

Contoh 1:

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

Penjelasan: Substring minimum "BANC" mencakup karakter 'A', 'B', dan 'C' dari string t.

Contoh 2:

Input: s = "a", t = "a"

Output: "a"

Penjelasan: Seluruh string s adalah minimum window.

Contoh 3:

Input: s = "a", t = "aa"

Output: ""

Penjelasan: Kedua karakter 'a' dari t harus dimasukkan dalam window. Karena window terbesar dari s hanya memiliki satu 'a', maka nilai yang dikembalikan berupa string kosong.

Batasan:

m == panjang s

n == panjang t

1 <= m, n <= 105

s dan t terdiri dari huruf besar dan kecil.

Solusi

def minWindow(self, s: str, t: str) -> str:
    if t == "": return ""

    countT, window = {}, {}

    for char in t:
        countT[char] = 1 + countT.get(char, 0)

    have, need = 0, len(countT)
    res, reslen = [-1, -1], float("infinity")
    left = 0

    for right in range(len(s)):
        char = s[right]
        window[char] = 1 + window.get(char, 0)

        if char in countT and window[char] == countT[char]:
            have += 1

        while have == need:
            if (right - left + 1) < reslen:
                res = [left, right]
                reslen = (right - left + 1)

            window[s[left]] -= 1
            if s[left] in countT and window[s[left]] < countT[s[left]]:
                have -= 1
            left += 1

    left, right = res
    return s[left:right+1] if reslen != float("infinity") else ""

Fungsi dimulai dengan memeriksa jika string t kosong, maka langsung mengembalikan string kosong.

Kemudian, dibuat dua buah dictionary countT dan window. countT digunakan untuk menyimpan jumlah kemunculan setiap karakter dalam string t, adapun window digunakan untuk menghimpun karakter yang ada di dalam window saat kita menelusuri keseluruhan string s.

Kemudian kita mengisi countT dengan jumlah kemunculan setiap karakter dalam string t. Ini berguna untuk memahami berapa banyak setiap karakter yang harus ada dalam window hasil.

Variabel have dan need dibuat untuk melacak jumlah karakter dalam window agar sesuai dengan yang diperlukan. have menghitung berapa banyak karakter yang sudah sesuai dengan t, sementara need akan menyimpan jumlah karakter yang diperlukan.

Variabel res digunakan untuk menyimpan indeks awal dan akhir dari minimum window, sedangkan reslen menyimpan panjang minimum window. Awalnya, res diatur ke [-1, -1] dan reslen diatur ke tak terhingga untuk mengawali pencarian minimum window.

Variabel left digunakan untuk melacak indeks awal dari jendela saat kita menggesernya melalui string s.

Selanjutnya, kita menggunakan dua pointer, yaitu left dan right, untuk menggeser jendela melalui string s. Kita juga akan memperbarui dictionary window untuk menghitung jumlah karakter dalam jendela saat ini.

Ketika kita menambahkan karakter ke dalam window, kita perlu memeriksa apakah karakter ini ada dalam countT. Jika demikian, kita perlu memeriksa juga apakah jumlah karakter dalam jendela saat ini sudah sama dengan jumlah yang diperlukan. Jika ya, maka kita meningkatkan have karena kita telah menemukan satu karakter yang diperlukan.

Ketika have sama dengan need, ini berarti window saat ini berisi semua karakter yang diperlukan. Pada saat ini, kita memeriksa apakah panjang window saat ini lebih pendek dari panjang minimum window yang ditemukan sejauh ini. Jika ya, kita memperbarui res dengan indeks left dan right, serta memperbarui reslen dengan panjang window saat ini.

Setelah itu, kita mulai menggeser window dengan mengurangi karakter di indeks left dari kamus window. Jika karakter ini adalah karakter yang dibutuhkan, kita juga memeriksa apakah pengurangan ini mengurangi jumlah karakter yang sesuai dengan yang diperlukan. Jika ya, kita mengurangi have karena karakter ini tidak lagi cukup dalam window. Selanjutnya, kita menggeser left ke kanan.

Terakhir, kita mengambil indeks left dan right dari minimum window yang ditemukan dan mengembalikan substring dari s yang sesuai dengan window tersebut. Jika tidak ada jendela yang ditemukan (dalam kasus ini, reslen masih tak terhingga), kita mengembalikan string kosong.

Secara keseluruhan, kode di atas mengimplementasikan algoritma Sliding Window untuk menemukan minimum window yang memenuhi syarat dari permasalahan yang diberikan.