Sliding Window Algorithm Paterns

Core Implementation Template

const slidingWindowSolution = (inputString) => {
    // Initialize tracking variables
    let [primaryVar, secondaryVar] = [initialValue1, initialValue2];
    
    // Set window boundaries
    let windowStart = 0;
    const results = [];
    
    for (let windowEnd = 0; windowEnd < inputString.length; windowEnd++) {
        // Update tracking variables with new element
        const currentChar = inputString[windowEnd];
        primaryVar = updatePrimary(primaryVar, currentChar);
        
        // Handle fixed-size window scenario
        if (windowEnd - windowStart + 1 > fixedSize) {
            // Adjust variables when exceeding size limit
            secondaryVar = adjustSecondary(secondaryVar, inputString[windowStart]);
            windowStart++;
        }
        
        // Handle variable-size window scenario
        while (isWindowInvalid(primaryVar, secondaryVar)) {
            // Shrink window until valid
            primaryVar = removeElement(primaryVar, inputString[windowStart]);
            windowStart++;
        }
        
        // Process valid window state
        if (isValidSolution(primaryVar, secondaryVar)) {
            results.push(windowStart);
        }
    }
    
    return results;
};

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring with out repeating characters.

Example:

Input: "abcabcbb"
Output: 3 // "abc"

Implementation:

const findLongestUniqueSubstring = (str) => {
    if (str.length === 0) return 0;
    
    let maxLength = 0;
    const charSet = new Set();
    let leftBoundary = 0;
    
    for (let rightBoundary = 0; rightBoundary < str.length; rightBoundary++) {
        const currentCharacter = str[rightBoundary];
        
        while (charSet.has(currentCharacter)) {
            charSet.delete(str[leftBoundary]);
            leftBoundary++;
        }
        
        charSet.add(currentCharacter);
        maxLength = Math.max(maxLength, rightBoundary - leftBoundary + 1);
    }
    
    return maxLength;
};

Finding All Anagrams in a String

Given two strings s and p, return all start indices of p's anagrams in s.

Example:

Input: s = "cbaebabacd", p = "abc"
Output: [0, 6] // "cba" and "bac"

Implemantation:

const locateAnagramPositions = (mainString, pattern) => {
    const resultIndices = [];
    const patternMap = new Map();
    const windowMap = new Map();
    
    // Build pattern frequency map
    for (const char of pattern) {
        patternMap.set(char, (patternMap.get(char) || 0) + 1);
    }
    
    let windowStart = 0;
    
    for (let windowEnd = 0; windowEnd < mainString.length; windowEnd++) {
        const currentChar = mainString[windowEnd];
        
        // Expand window
        windowMap.set(currentChar, (windowMap.get(currentChar) || 0) + 1);
        
        // Handle invalid characters
        if (!patternMap.has(currentChar)) {
            while (windowStart <= windowEnd) {
                const startChar = mainString[windowStart];
                windowMap.set(startChar, windowMap.get(startChar) - 1);
                windowStart++;
            }
            continue;
        }
        
        // Handle character frequency excess
        while (windowMap.get(currentChar) > patternMap.get(currentChar)) {
            const startChar = mainString[windowStart];
            windowMap.set(startChar, windowMap.get(startChar) - 1);
            windowStart++;
        }
        
        // Maintain window size constraint
        while (windowEnd - windowStart + 1 > pattern.length) {
            const startChar = mainString[windowStart];
            windowMap.set(startChar, windowMap.get(startChar) - 1);
            windowStart++;
        }
        
        // Check for anagram match
        if (windowEnd - windowStart + 1 === pattern.length) {
            resultIndices.push(windowStart);
        }
    }
    
    return resultIndices;
};