Maximum Substring Frequency

Problem Statement: Given a string s, determine the maximum frequency of any substring that satisfies the following constraints:

1. The number of unique characters in the substring must not exceed maxLetters.
2. The length of the substring must be between minSize and maxSize (inclusive).

Example 1: Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4 Output: 2 Explanation: The substring "aab" appears twice. It has 2 distinct characters and a length of 3.

Optimization Insight: Since any longer substring satisfying the condition contains a shorter substring of length minSize that also satisfies the condition with at least the same character count, it is sufficient to only check substrings of length minSize. Checking longer strings does not yield a higher frequency than their prefixes.

Implementation:

/**
 * @param {string} inputString
 * @param {number} charLimit
 * @param {number} minLength
 * @param {number} maxLength
 * @return {number}
 */
var maxOccurrences = function(inputString, charLimit, minLength, maxLength) {
    const frequencyMap = new Map();
    let maxCount = 0;

    for (let i = 0; i <= inputString.length - minLength; i++) {
        const candidate = inputString.slice(i, i + minLength);
        
        // Count unique characters efficiently
        const uniqueChars = new Set(candidate.split(''));
        
        if (uniqueChars.size <= charLimit) {
            const currentFreq = (frequencyMap.get(candidate) || 0) + 1;
            frequencyMap.set(candidate, currentFreq);
            maxCount = Math.max(maxCount, currentFreq);
        }
    }
    return maxCount;
};

---

Partitioning into Consecutive Sets

Problem Statement: Given an array of integers nums and a positive integer k, determine whether it is possible to partition the array into disjoint sets where each set consists of k consecutive numbers.

Examples:

• Input: nums = [1,2,3,3,4,4,5,6], k = 4 Output: true (Sets: [1,2,3,4] and [3,4,5,6])
• Input: nums = [1,2,3,4], k = 3 Output: false

Approach: The core logic involves processing numbers in sorted order. For every smallest available number x, we must find x+1, x+2, ..., x+k-1. If any of these are missing or exhausted, the partition is impossible. Using a frequency map (hash map) alows O(1) checks and decrements compared to O(N) array splicing.

Implementation:

/**
 * @param {number[]} numbers
 * @param {number} groupSize
 * @return {boolean}
 */
var canDivide = function(numbers, groupSize) {
    if (numbers.length % groupSize !== 0) {
        return false;
    }

    const countMap = new Map();
    numbers.forEach(num => {
        countMap.set(num, (countMap.get(num) || 0) + 1);
    });

    const sortedKeys = Array.from(countMap.keys()).sort((a, b) => a - b);

    for (const num of sortedKeys) {
        const count = countMap.get(num);
        if (count > 0) {
            for (let i = 0; i < groupSize; i++) {
                const nextVal = num + i;
                if ((countMap.get(nextVal) || 0) < count) {
                    return false;
                }
                countMap.set(nextVal, countMap.get(nextVal) - count);
            }
        }
    }
    return true;
};

---

Maximum Candy Collection from Boxes

Problem Statement: You are given boxes, each having properties regarding its open status, candies inside, keys contained within, and other boxes stored inside it. You start with a specific set of boxes (initialBoxes). Return the maximum total candies you can collect.

Constraints & Rules:

• You can only open a box if its already open or if you possess the key found previously.
• Opening a box provides its candies, any keys inside, and access to contained boxes.
• A box cannot be counted more than once.

Strategy: This problem is best solved using Breadth-First Search (BFS). We maintain a queue of accessible boxes. As we process each box, we update our collection of found keys. Any newly discovered boxes are added to the pool of candidates. We iterate until no new boxes can be opened due to a lack of keys or unavailability.

Implementation:

/**
 * @param {number[]} initialStatus
 * @param {number[]} rewardAmounts
 * @param {number[][]} foundKeys
 * @param {number[][]} nestedBoxIds
 * @param {number[]} startingBoxes
 * @return {number}
 */
var getMaxCandies = function(initialStatus, rewardAmounts, foundKeys, nestedBoxIds, startingBoxes) {
    const openedSet = new Set();
    const keyPool = new Set();
    const toProcess = [...startingBoxes];
    let totalCollected = 0;

    while (toProcess.length > 0) {
        const boxId = toProcess.pop();

        if (openedSet.has(boxId)) continue;

        // Check if we have the authority to open this box
        const isOpenedInit = initialStatus[boxId] === 1;
        const hasKey = keyPool.has(boxId);

        if (isOpenedInit || hasKey) {
            openedSet.add(boxId);
            totalCollected += rewardAmounts[boxId];

            // Collect keys from this box
            foundKeys[boxId].forEach(keyId => keyPool.add(keyId));

            // Add internal boxes to the processing queue
            nestedBoxIds[boxId].forEach(innerBox => {
                if (!openedSet.has(innerBox)) {
                    toProcess.push(innerBox);
                }
            });
        }
    }

    return totalCollected;
};