Leetcode 76 Minimum Window Substring

Soru

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.

The testcases will be generated such that the answer is unique.

Örnek 1

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Örnek 2

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Örnek 3

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Çözüm

• Verilen iki string s ve t arasında, t içindeki tüm karakterleri kapsayan s stringinin en küçük alt dizisini bulmanızı ister. Bu alt dizi, t stringindeki tüm karakterleri içeren s stringinden alınmış en kısa ardışık dizi olmalıdır.
• Girdi: İki string, s ve t.
• Çıktı: s içinde, t içindeki tüm karakterleri içeren en küçük alt dizi. Eğer böyle bir alt dizi yoksa boş string döndürülür.
• Bu problem genellikle kaydırmalı pencere (sliding window) ve hash map kullanılarak çözülür. t stringindeki karakterlerin frekanslarını bir hash map’te saklayarak başlanır. Ardından, s üzerinde bir pencere kaydırarak bu pencerenin t stringindeki tüm karakterleri içerip içermediğini kontrol edersiniz. Pencere, t’deki tüm karakterleri kapsadığında, bu pencereyi olabildiğince daraltarak en küçük alt diziyi bulmaya çalışırsınız.
• Çalışma Mekanizması:
• İnitialize: dict_t t’deki karakterlerin frekansını saklar. required t’deki benzersiz karakter sayısını, formed ise şu an pencerede bulunan ve t’deki karakterleri karşılayan karakter sayısını tutar.
• Kaydırmalı Pencere: s üzerinde r (sağ) işaretçisiyle ilerlerken, pencereye karakterler eklenir. Her karakter için, window_counts güncellenir.
• Pencereyi Daraltma: Pencere t’deki tüm karakterleri içerdiğinde, l (sol) işaretçisiyle pencere daraltılarak mümkün olan en küçük boyut aranır.
• Sonuç Dönüşü: Eğer bir sonuç bulunmuşsa, bu sonuç döndürülür. Bulunamamışsa boş string döndürülür.

Code

from collections import Counter

class Solution:
    def minWindow(self, s, t):
        if not t or not s:
            return ""

        dict_t = Counter(t)
        required = len(dict_t)
        l, r = 0, 0
        formed = 0
        window_counts = {}

        ans = float("inf"), None, None  # Pencerenin boyutu, başlangıç ve bitiş indeksleri

        while r < len(s):
            character = s[r]
            window_counts[character] = window_counts.get(character, 0) + 1

            if character in dict_t and window_counts[character] == dict_t[character]:
                formed += 1

            while l <= r and formed == required:
                character = s[l]

                if r - l + 1 < ans[0]:
                    ans = (r - l + 1, l, r)

                window_counts[character] -= 1
                if character in dict_t and window_counts[character] < dict_t[character]:
                    formed -= 1

                l += 1    

            r += 1

        return "" if ans[0] == float("inf") else s[ans[1]:ans[2] + 1]
     
        

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(S + T), burada S ve T sırasıyla s ve t stringlerinin uzunluklarıdır.
• Space complexity (Alan Karmaşıklığı) : O(S + T), hash map için kullanılan alan nedeniyle.