Leetcode 567 Permutation in String

Soru

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

Örnek 1

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Örnek 2

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Çözüm

• Bir stringin (s1) permutasyonunun, başka bir string (s2) içinde alt dizi olarak bulunup bulunmadığını belirlemenizi ister. Bu, esasen s1’in herhangi bir permutasyonunun s2 içinde olup olmadığını kontrol etmek anlamına gelir.
• Girdi: İki string, s1 ve s2.
• Çıktı: Eğer s1’in herhangi bir permutasyonu s2 içinde varsa true, aksi takdirde false.
• Bu problem, kaydırmalı pencere (sliding window) ve hash map kullanılarak çözülebilir. s1 stringinin karakter frekanslarını bir hash map’te saklayarak başlanır, ardından s2 üzerinde bir pencere boyutu s1.length() ile kaydırılarak her pencere için karakter frekansları karşılaştırılır. Eğer herhangi bir noktada, s2’nin alt dizisinin karakter dağılımı s1 ile aynıysa, bu bir eşleşme olarak kabul edilir.
• Çalışma Mekanizması:
• Başlangıç Kontrolü: Eğer s1’in uzunluğu s2’den büyükse, s2 içinde s1’in permutasyonu olamaz.
• Karakter Sayma: s1 için bir Counter kullanılarak karakter frekansları hesaplanır.
• Kaydırmalı Pencere: s2 üzerinde bir döngü ile geçilir ve her adımda pencereye bir karakter eklenir. Pencerenin boyutu s1’in uzunluğundan fazla olursa, pencerenin başındaki karakter çıkarılır.
• Frekans Karşılaştırması: Her adımda, pencerenin frekans dağılımı s1’in frekans dağılımı ile karşılaştırılır. Eşleşme olması durumunda true dönülür.
• Sonuç: Eğer döngü sonunda hiçbir eşleşme bulunamazsa, false dönülür.

Code

from collections import Counter

class Solution:
    def checkInclusion(self, s1, s2):
        if len(s1) > len(s2):
            return False

        s1_count = Counter(s1)
        window_count = Counter()

        for i in range(len(s2)):
            # Pencereye yeni bir karakter ekle
            window_count[s2[i]] += 1

            # Pencere boyutunu s1'in uzunluğunda tut
            if i >= len(s1):
                if window_count[s2[i - len(s1)]] == 1:
                    del window_count[s2[i - len(s1)]]
                else:
                    window_count[s2[i - len(s1)]] -= 1

            # Pencerenin ve s1_count'un karşılaştırılması
            if window_count == s1_count:
                return True

        return False      
        

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(n + m), burada n s2’nin uzunluğu ve m s1’in uzunluğudur. Her karakter için sabit zamanlı işlemler yapılır.
• Space complexity (Alan Karmaşıklığı) : O(1), çünkü kullanılan veri yapıları sabit sayıda karakteri tutar ve bu sayı sınırlıdır.