Anagram Substring Search ใน Java: Sliding Window + Character Count

Anagram Substring Search

หา ทุกตำแหน่ง ใน Text ที่มี Substring เป็น Anagram (ตัวอักษรเหมือนกัน ลำดับต่างได้) ของ Pattern

ตัวอย่างโค้ด

public class Demo { 
    static final int MAX_CHAR = 256; // ASCII
    
    // เปรียบเทียบ character count arrays
    static boolean compareCounts(int[] count1, int[] count2) { 
        for (int i = 0; i < MAX_CHAR; i++) 
            if (count1[i] != count2[i]) 
                return false; 
        return true; 
    } 
    
    // Sliding Window + Character Count
    static void searchAnagram(String pattern, String text) { 
        int m = pattern.length(); 
        int n = text.length(); 
        
        if (m > n) return; 
        
        int[] countPat = new int[MAX_CHAR]; 
        int[] countTxt = new int[MAX_CHAR]; 
        
        // Initialize counts for first window
        for (int i = 0; i < m; i++) { 
            countPat[pattern.charAt(i)]++; 
            countTxt[text.charAt(i)]++; 
        } 
        
        // Slide window
        for (int i = m; i < n; i++) { 
            // Check current window
            if (compareCounts(countPat, countTxt)) 
                System.out.println("พบที่ index " + (i - m)); 
            
            // Add new char
            countTxt[text.charAt(i)]++; 
            // Remove old char
            countTxt[text.charAt(i - m)]--; 
        } 
        
        // Check last window
        if (compareCounts(countPat, countTxt)) 
            System.out.println("พบที่ index " + (n - m)); 
    } 
    
    public static void main(String[] args) { 
        String text = "ABNFGHABNJGH"; 
        String pattern = "NFGH"; 
        searchAnagram(pattern, text); 
    } 
}

ผลลัพธ์

พบที่ index 2

คำอธิบาย

Text: ABNFGHABNJGH, Pattern: NFGH (length 4)

Window indices:
0-3: ABNF  -> counts: A,B,N,F
1-4: BNFG  -> counts: B,N,F,G
2-5: NFGH  -> counts: N,F,G,H ✓ MATCH (index 2)
3-6: FGHA  -> counts: F,G,H,A
4-7: GHAB  -> counts: G,H,A,B
5-8: HABN  -> counts: H,A,B,N
6-9: ABNJ  -> counts: A,B,N,J
7-10: BNJG -> counts: B,N,J,G
8-11: NJGH -> counts: N,J,G,H

อัลกอริทึม: Sliding Window + Frequency Count

1. นับความถี่ตัวอักษรใน Pattern (countPat)
2. นับความถี่ใน Window แรกของ Text (countTxt)
3. Slide window: เพิ่มตัวใหม่ ลบตัวเก่า อัปเดต countTxt O(1)
4. เปรียบเทียบ countPat กับ countTxt O(256) = O(1)

ความซับซ้อน

การปรับปรุง: ใช้ Match Count แทน Compare Array

// แทนที่ compareCounts() ทุกครั้ง
// เก็บตัวแปร matchCount = จำนวน character ที่ count ตรงกัน
// อัปเดต matchCount เมื่อ add/remove char -> O(1) ต่อ window

Unicode Support

// สำหรับ Unicode ใช้ Map แทน array
Map countPat = new HashMap<>(); 
Map countWin = new HashMap<>(); 
// เปรียบเทียบด้วย equals() หรือ maintain match count

Related Problems

• LeetCode 438: Find All Anagrams in a String
• Permutation in String (LeetCode 567)
• Minimum Window Substring (LeetCode 76)