โปรแกรมหาดัชนีเริ่มต้นของทั้งหมดของอนุกรม (Anagrams) ของสตริง S ใน T ด้วย Python

ปัญหา

กำหนดสตริงสองตัว S และ T ต้องการหา index เริ่มต้นทั้งหมดของ anagrams ของ S ที่ปรากฏใน T สตริงประกอบด้วยตัวพิมพ์เล็ก בלבד ความยาว S ≤ 20, T ≤ 100

ตัวอย่าง: S = "cab", T = "bcabxabc" → ผลลัพธ์ [0, 1, 5] เพราะ substring "bca", "cab", "abc" เป็น anagrams ของ "cab"

อัลกอริทึม (Sliding Window + Hash Map)

1. สร้าง map m เก็บความถี่ตัวอักษรใน S
2. ตัวแปร: n = ความยาว T, left=0, right=0, counter = ความยาว S
3. ลูป right จาก 0 ถึง n-1:
   • ถ้า T[right] อยู่ใน map และ count > 0: ลด count, ลด counter, ถ้า counter=0 → เพิ่ม left ลงคำตอบ
   • ถ้าไม่: ขยับ left ไปข้างหน้าจนกว่าจะ valid อีกครั้ง (ปรับ count และ counter)
4. คืนค่าลิสต์ index เริ่มต้น

การนำไปใช้ (Python)

class Solution:
    def findAnagrams(self, s: str, p: str):
        from collections import Counter
        m = Counter(p)
        n = len(s)
        left = 0
        counter = len(p)
        ans = []
        
        for right in range(n):
            if m.get(s[right], 0) > 0:
                m[s[right]] -= 1
                counter -= 1
                if counter == 0:
                    ans.append(left)
            else:
                while left < right:
                    if m.get(s[left], 0) >= 0:
                        m[s[left]] += 1
                        counter += 1
                    left += 1
                    if m.get(s[right], 0) > 0:
                        right -= 1  # compensate for loop increment
                        break
                if m.get(s[left], 0) == 0:
                    left = right + 1
        return ans

# Test
ob = Solution()
print(ob.findAnagrams("bcabxabc", "cab"))  # [0, 1, 5]

อธิบาย

ใช้ sliding window ความยาวเท่ากับ S รวมกับ hash map นับความถี่ตัวอักษร เมื่อ window มีตัวอักษรครบตาม S (counter=0) บันทึก index เริ่มต้น

ตัวอย่าง C++ ในต้นฉบับซับซ้อนกว่า Python version นี้เขียนใหม่ให้อ่านง่ายและ Pythonic