Hashing Problems and Solutions

Find the First Non-Repeating Character in a String

function firstNonRepeatingCharacter(str) {
    let freqMap = {};
    
    // Count frequency of each character
    for (let char of str) {
        freqMap[char] = (freqMap[char] || 0) + 1;
    }
    
    // Find first non-repeating character
    for (let char of str) {
        if (freqMap[char] === 1) {
            return char;
        }
    }
    
    return null; // No non-repeating character
}

Count Distinct Elements in a Window

function countDistinctInWindow(arr, k) {
    let freqMap = {};
    let result = [];
    
    for (let i = 0; i < k; i++) {
        freqMap[arr[i]] = (freqMap[arr[i]] || 0) + 1;
    }
    
    result.push(Object.keys(freqMap).length);

    for (let i = k; i < arr.length; i++) {
        freqMap[arr[i - k]]--;
        if (freqMap[arr[i - k]] === 0) {
            delete freqMap[arr[i - k]];
        }
        freqMap[arr[i]] = (freqMap[arr[i]] || 0) + 1;
        result.push(Object.keys(freqMap).length);
    }
    
    return result;
}

Check if Two Strings Are Anagrams of Each Other

function areAnagrams(str1, str2) {
    if (str1.length !== str2.length) {
        return false;
    }
    
    let freqMap = {};
    
    for (let char of str1) {
        freqMap[char] = (freqMap[char] || 0) + 1;
    }
    
    for (let char of str2) {
        if (!freqMap[char]) {
            return false;
        }
        freqMap[char]--;
    }
    
    return true;
}

Find Pairs with a Given Sum in an Array

function findPairsWithSum(arr, sum) {
    let freqMap = {};
    let result = [];
    
    for (let num of arr) {
        let complement = sum - num;
        if (freqMap[complement]) {
            result.push([complement, num]);
        }
        freqMap[num] = (freqMap[num] || 0) + 1;
    }
    
    return result;
}

Subarray with Given Sum (Using Hash Map)

function subarrayWithGivenSum(arr, targetSum) {
    let sumMap = new Map();
    let currentSum = 0;
    
    for (let i = 0; i < arr.length; i++) {
        currentSum += arr[i];
        
        if (currentSum === targetSum) {
            return arr.slice(0, i + 1);
        }
        
        if (sumMap.has(currentSum - targetSum)) {
            return arr.slice(sumMap.get(currentSum - targetSum) + 1, i + 1);
        }
        
        sumMap.set(currentSum, i);
    }
    
    return null; // No subarray found
}

Longest Subarray with At Most K Distinct Characters

function longestSubarrayWithKDistinctChars(str, k) {
    let freqMap = {};
    let left = 0;
    let maxLength = 0;
    
    for (let right = 0; right < str.length; right++) {
        freqMap[str[right]] = (freqMap[str[right]] || 0) + 1;
        
        while (Object.keys(freqMap).length > k) {
            freqMap[str[left]]--;
            if (freqMap[str[left]] === 0) {
                delete freqMap[str[left]];
            }
            left++;
        }
        
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

Group Anagrams Together

function groupAnagrams(strs) {
    let result = {};
    
    for (let str of strs) {
        let sortedStr = str.split('').sort().join('');
        if (!result[sortedStr]) {
            result[sortedStr] = [];
        }
        result[sortedStr].push(str);
    }
    
    return Object.values(result);
}

Implement a Hash Map

class HashMap {
    constructor() {
        this.map = new Array(100);
    }

    hash(key) {
        let hashCode = 0;
        for (let i = 0; i < key.length; i++) {
            hashCode = (hashCode + key.charCodeAt(i)) % this.map.length;
        }
        return hashCode;
    }

    set(key, value) {
        let index = this.hash(key);
        this.map[index] = this.map[index] || [];
        this.map[index].push([key, value]);
    }

    get(key) {
        let index = this.hash(key);
        if (this.map[index]) {
            for (let [k, v] of this.map[index]) {
                if (k === key) {
                    return v;
                }
            }
        }
        return undefined;
    }

    remove(key) {
        let index = this.hash(key);
        if (this.map[index]) {
            this.map[index] = this.map[index].filter(([k, _]) => k !== key);
        }
    }
}