0567_permutation_in_string.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Permutation in String - LeetCode 567</title>
    <link rel="stylesheet" href="styles.css">
    <script src="https://d3js.org/d3.v7.min.js"></script>
</head>
<body>
    <div class="container">
        <div class="problem-info">
            <h1><span class="problem-number">#567</span> Permutation in String</h1>
            <p>Check if s2 contains any permutation of s1 as a substring. Use a sliding window with character frequency matching!</p>
            <div class="problem-meta">
                <span class="meta-tag">🪟 Sliding Window</span>
                <span class="meta-tag">🔤 String</span>
                <span class="meta-tag">⏱️ O(n)</span>
            </div>
            <div class="file-ref">
                📄 Python: <a href="../python/0567_permutation_in_string/0567_permutation_in_string.py">0567_permutation_in_string.py</a>
            </div>
            </div>

        <div class="explanation-panel">
            <h4>💡 How It Works (Layman's Terms)</h4>
            <ul>
                <li><strong>Permutation:</strong> Same characters in any order (e.g., "ab" and "ba" are permutations)</li>
                <li><strong>Key insight:</strong> Two strings are permutations if they have the same character frequencies</li>
                <li><strong>Window size:</strong> Always equals len(s1) - a permutation must have the same length</li>
                <li><strong>Slide window:</strong> Move window one character at a time, updating frequencies</li>
                <li><strong>Match found:</strong> When window's char frequencies equal s1's frequencies</li>
            </ul>
        </div>


        <div class="visualization-section">
            <h3>🎬 Step-by-Step Visualization</h3>
            
            <div class="controls">
                <button class="btn btn-primary" id="stepBtn" onclick="step()">Step</button>
                <button class="btn btn-success" id="autoBtn" onclick="toggleAuto()">Auto Run</button>
                <button class="btn btn-warning" onclick="reset()">Reset</button>
            </div>

            <div class="status-message" id="statusMessage">
                Click "Step" or "Auto Run" to check if s2 contains a permutation of s1
            </div>

            <div class="array-section">
                <div class="array-label">s1 (pattern to find permutation of):</div>
                <div class="array-container" id="s1Container"></div>
            </div>

            <div class="array-section">
                <div class="array-label">s2 (search in this string):</div>
                <div class="array-container" id="s2Container"></div>
            </div>

            <div style="display: flex; gap: 30px; margin-top: 20px;">
                <div class="array-section" style="flex: 1;">
                    <div class="array-label">s1 Character Counts:</div>
                    <div id="s1CountContainer" style="display: flex; gap: 10px; flex-wrap: wrap;"></div>
                </div>
                <div class="array-section" style="flex: 1;">
                    <div class="array-label">Current Window Counts:</div>
                    <div id="windowCountContainer" style="display: flex; gap: 10px; flex-wrap: wrap;"></div>
                </div>
            </div>

            <div class="info-box" id="matchBox" style="display: none;"></div>
        </div>
        <div class="code-section">
            <h3>💻 Python Solution</h3>
            <div class="code-block">
                <pre>from typing import List
from collections import Counter


"""
LeetCode Permutation In String

Problem from LeetCode: https://leetcode.com/problems/permutation-in-string/

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.

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

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

Constraints:
    1 &lt;= s1.length, s2.length &lt;= 10^4
    s1 and s2 consist of lowercase English letters.
"""

class Solution:

    def check_inclusion(self, s1: str, s2: str) -&gt;bool:
        """
        Check if s2 contains a permutation of s1.
        
        Args:
            s1: First string
            s2: Second string
            
        Returns:
            bool: True if s2 contains a permutation of s1, False otherwise
        """
        if len(s1) &gt; len(s2):
            return False
        s1_map = [0] * 26
        s2_map = [0] * 26
        for i in range(len(s1)):
            s1_map[ord(s1[i]) - ord('a')] += 1
            s2_map[ord(s2[i]) - ord('a')] += 1
        for i in range(len(s2) - len(s1)):
            if self._matches(s1_map, s2_map):
                return True
            s2_map[ord(s2[i + len(s1)]) - ord('a')] += 1
            s2_map[ord(s2[i]) - ord('a')] -= 1
        return self._matches(s1_map, s2_map)

    def _matches(self, s1_map: List[int], s2_map: List[int]) -&gt;bool:
        """
        Check if two frequency maps match.
        
        Args:
            s1_map: Frequency map for s1
            s2_map: Frequency map for s2
            
        Returns:
            bool: True if the maps match, False otherwise
        """
        for i in range(26):
            if s1_map[i] != s2_map[i]:
                return False
        return True

    def checkInclusion_counter(self, s1: str, s2: str) -&gt;bool:
        """
        Check if s2 contains a permutation of s1 using Counter.
        
        Args:
            s1: First string
            s2: Second string
            
        Returns:
            bool: True if s2 contains a permutation of s1, False otherwise
        """
        if len(s1) &gt; len(s2):
            return False
        s1_counter = Counter(s1)
        window_size = len(s1)
        window_counter = Counter(s2[:window_size])
        if window_counter == s1_counter:
            return True
        for i in range(len(s2) - window_size):
            window_counter[s2[i]] -= 1
            if window_counter[s2[i]] == 0:
                del window_counter[s2[i]]
            window_counter[s2[i + window_size]] += 1
            if window_counter == s1_counter:
                return True
        return False

    def checkInclusion_optimized(self, s1: str, s2: str) -&gt;bool:
        """
        Optimized sliding window approach with a single comparison.
        
        Args:
            s1: First string
            s2: Second string
            
        Returns:
            bool: True if s2 contains a permutation of s1, False otherwise
        """
        if len(s1) &gt; len(s2):
            return False
        counter = Counter(s1)
        matches = 0
        required = len(counter)
        for i in range(len(s1)):
            char = s2[i]
            if char in counter:
                counter[char] -= 1
                if counter[char] == 0:
                    matches += 1
        if matches == required:
            return True
        for i in range(len(s1), len(s2)):
            add_char = s2[i]
            if add_char in counter:
                counter[add_char] -= 1
                if counter[add_char] == 0:
                    matches += 1
            remove_char = s2[i - len(s1)]
            if remove_char in counter:
                if counter[remove_char] == 0:
                    matches -= 1
                counter[remove_char] += 1
            if matches == required:
                return True
        return False


if __name__ == '__main__':
    # Example usage based on LeetCode sample
    solution = Solution()
    
    # Example 1: s1 = "ab", s2 = "eidbaooo"
    print("Example 1:")
    result = solution.check_inclusion("ab", "eidbaooo")
    print(f"Output: {result}")  # Expected: True
    
    # Example 2: s1 = "ab", s2 = "eidboaoo"
    print("\nExample 2:")
    result = solution.check_inclusion("ab", "eidboaoo")
    print(f"Output: {result}")  # Expected: False
    
    # Test with alternative implementations
    print("\nAlternative implementations:")
    print("Counter approach:", solution.checkInclusion_counter("ab", "eidbaooo"))
    print("Optimized approach:", solution.checkInclusion_optimized("ab", "eidbaooo"))
</pre>
            </div>
        </div>

        </div>

    <script>
        const s1 = "ab";
        const s2 = "eidbaooo";
        const windowSize = s1.length;
        
        let s1Count = {};
        let windowCount = {};
        let windowStart = 0;
        let phase = 'init';
        let autoInterval = null;

        function getCount(str) {
            const count = {};
            for (const c of str) {
                count[c] = (count[c] || 0) + 1;
            }
            return count;
        }

        function countsMatch(c1, c2) {
            const keys1 = Object.keys(c1).filter(k => c1[k] > 0);
            const keys2 = Object.keys(c2).filter(k => c2[k] > 0);
            if (keys1.length !== keys2.length) return false;
            for (const k of keys1) {
                if (c1[k] !== c2[k]) return false;
            }
            return true;
        }

        function init() {
            s1Count = getCount(s1);
            windowCount = {};
            windowStart = 0;
            renderS1();
            renderS2();
            renderCounts();
            document.getElementById('matchBox').style.display = 'none';
        }

        function renderS1() {
            const container = document.getElementById('s1Container');
            container.innerHTML = '';
            s1.split('').forEach((char, idx) => {
                const box = document.createElement('div');
                box.className = 'array-box';
                box.style.width = '45px';
                box.innerHTML = `${char}<span class="index-label">[${idx}]</span>`;
                container.appendChild(box);
            });
        }

        function renderS2() {
            const container = document.getElementById('s2Container');
            container.innerHTML = '';
            s2.split('').forEach((char, idx) => {
                const box = document.createElement('div');
                box.className = 'array-box';
                box.id = `s2-${idx}`;
                box.style.width = '45px';
                if (idx >= windowStart && idx < windowStart + windowSize) {
                    box.classList.add('current');
                }
                box.innerHTML = `${char}<span class="index-label">[${idx}]</span>`;
                container.appendChild(box);
            });
        }

        function renderCounts() {
            const s1Container = document.getElementById('s1CountContainer');
            s1Container.innerHTML = '';
            Object.entries(s1Count).sort().forEach(([char, count]) => {
                const box = document.createElement('div');
                box.className = 'variable-box';
                box.innerHTML = `<div class="variable-name">'${char}'</div><div class="variable-value">${count}</div>`;
                s1Container.appendChild(box);
            });

            const windowContainer = document.getElementById('windowCountContainer');
            windowContainer.innerHTML = '';
            const windowKeys = Object.keys(windowCount).filter(k => windowCount[k] > 0).sort();
            if (windowKeys.length === 0) {
                windowContainer.innerHTML = '<span style="color: #999;">Empty</span>';
            } else {
                windowKeys.forEach(char => {
                    const box = document.createElement('div');
                    box.className = 'variable-box';
                    const matches = s1Count[char] === windowCount[char];
                    if (matches) {
                        box.style.borderColor = '#4caf50';
                        box.style.background = '#e8f5e9';
                    } else {
                        box.style.borderColor = '#ff9800';
                        box.style.background = '#fff3e0';
                    }
                    box.innerHTML = `<div class="variable-name">'${char}'</div><div class="variable-value">${windowCount[char]}

        </div>`;
                    windowContainer.appendChild(box);
                });
            }
        }

        function step() {
            if (phase === 'init') {
                phase = 'firstWindow';
                windowCount = getCount(s2.substring(0, windowSize));
                renderS2();
                renderCounts();
                
                if (countsMatch(s1Count, windowCount)) {
                    phase = 'found';
                    document.getElementById('matchBox').style.display = 'block';
                    document.getElementById('matchBox').className = 'info-box secondary';
                    document.getElementById('matchBox').textContent = `✅ Found! "${s2.substring(0, windowSize)}" is a permutation of "${s1}"`;
                    document.getElementById('statusMessage').textContent = 'Permutation found in first window!';
                    document.getElementById('stepBtn').disabled = true;
                    stopAuto();
                } else {
                    document.getElementById('statusMessage').textContent = 
                        `Initial window "${s2.substring(0, windowSize)}": Counts don't match s1. Sliding...`;
                }
                return;
            }

            if (phase === 'firstWindow') {
                phase = 'sliding';
            }

            if (phase === 'sliding') {
                if (windowStart >= s2.length - windowSize) {
                    phase = 'done';
                    document.getElementById('matchBox').style.display = 'block';
                    document.getElementById('matchBox').className = 'info-box highlight';
                    document.getElementById('matchBox').textContent = '❌ No permutation of s1 found in s2';
                    document.getElementById('statusMessage').textContent = 'Search complete. No match found.';
                    document.getElementById('stepBtn').disabled = true;
                    stopAuto();
                    return;
                }

                // Slide window
                const removeChar = s2[windowStart];
                windowCount[removeChar]--;
                if (windowCount[removeChar] === 0) delete windowCount[removeChar];
                
                windowStart++;
                const addChar = s2[windowStart + windowSize - 1];
                windowCount[addChar] = (windowCount[addChar] || 0) + 1;

                renderS2();
                renderCounts();

                const windowStr = s2.substring(windowStart, windowStart + windowSize);
                
                if (countsMatch(s1Count, windowCount)) {
                    phase = 'found';
                    document.getElementById('matchBox').style.display = 'block';
                    document.getElementById('matchBox').className = 'info-box secondary';
                    document.getElementById('matchBox').textContent = `✅ Found! "${windowStr}" is a permutation of "${s1}"`;
                    document.getElementById('statusMessage').textContent = `Permutation found at position ${windowStart}!`;
                    document.getElementById('stepBtn').disabled = true;
                    stopAuto();
                } else {
                    document.getElementById('statusMessage').textContent = 
                        `Window "${windowStr}" at [${windowStart}]: Removed '${removeChar}', added '${addChar}'. Counts don't match.`;
                }
            }
        }

        function toggleAuto() {
            if (autoInterval) {
                stopAuto();
            } else {
                document.getElementById('autoBtn').textContent = 'Pause';
                autoInterval = setInterval(() => {
                    if (phase === 'done' || phase === 'found') {
                        stopAuto();
                    } else {
                        step();
                    }
                }, 1200);
            }
        }

        function stopAuto() {
            if (autoInterval) {
                clearInterval(autoInterval);
                autoInterval = null;
            }
            document.getElementById('autoBtn').textContent = 'Auto Run';
        }

        function reset() {
            stopAuto();
            phase = 'init';
            windowStart = 0;
            document.getElementById('stepBtn').disabled = false;
            document.getElementById('statusMessage').textContent = 
                'Click "Step" or "Auto Run" to check if s2 contains a permutation of s1';
            init();
        }

        init();
    </script>
</body>
</html>