Sliding Window Maximum Sum Subarray

LongestSubstringKDistinct.java

import java.util.*;

class LongestSubstringKDistinct {
  public static int findLength(String str, int k) {
    int windowStart = 0, maxLength = 0;
    Map<Character, Integer> charFrequencyMap = new HashMap<>();
    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
      char rightChar = str.charAt(windowEnd);
      charFrequencyMap.put(rightChar, charFrequencyMap.getOrDefault(rightChar, 0) + 1);

      while (charFrequencyMap.size() > k) {
        char leftChar = str.charAt(windowStart);
        charFrequencyMap.put(leftChar, charFrequencyMap.get(leftChar) - 1);
        if (charFrequencyMap.get(leftChar) == 0) {
          charFrequencyMap.remove(leftChar);
        }
        windowStart++;
      }
      maxLength = Math.max(maxLength, windowEnd - windowStart + 1); 
    }

MaxSumSubarray.java

package slidingwindow;

/**
 * Find the max sum subarray of a fixed size K
 *
 * Example input:
 * [4, 2, 1, 7, 8, 1, 2, 8, 1, 0]
 *
 */
public class MaxSumSubarray {

    public static int findMaxSumSubarray(int[] arr, int k) {
        int maxValue = Integer.MIN_VALUE;
        int currentRunningSum = 0;

        for (int i = 0; i < arr.length; i++) {
            currentRunningSum += arr[i];

            if (i >= k - 1) {
                maxValue = Math.max(maxValue, currentRunningSum);
                currentRunningSum -= arr[i - (k - 1)];
            }
        }

        return maxValue;
    }


    public static void main(String[] args) {
        System.out.println(findMaxSumSubarray(new int[]{4, 2, 1, 7, 8, 1, 2, 8, 1, 0}, 3));
    }
}

SmallestSubarrayGivenSum.java

package slidingwindow;

public class SmallestSubarrayGivenSum {

    public static int smallestSubarray(int targetSum, int[] arr) {
        int minWindowSize = Integer.MAX_VALUE;
        int currentWindowSum = 0;
        int windowStart = 0;
        for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
            currentWindowSum += arr[windowEnd];

            while(currentWindowSum >= targetSum) {
                minWindowSize = Math.min(minWindowSize, windowEnd - windowStart + 1);
                currentWindowSum -= arr[windowStart];
                windowStart++;
            }
        }

        return minWindowSize;
    }

    public static void main(String[] args) {
        int[] input = new int[]{4,2,2,7,8,1,2,8,10};
        int targetSum = 8;
        System.out.println(smallestSubarray(targetSum, input));
    }
}

For SmallestSubarrayGivenSum.java, the current implementation finds the minimum window size for a value >= the target sum.

Example:

int[] input = new int[]{1, 1, 4, 3, -1};
int targetSum = 2;

Will yield 1 as a result (4 or 3)

For anyone that wants to find the smallest window size for the target sum reliably:

Change minWindowSize = Math.min(minWindowSize, windowEnd - windowStart + 1); to be:

if (currentWindowSum == targetSum) {
    minWindowSize = Math.min(minWindowSize, (windowEnd - windowStart) + 1);
}

With the small change above, the original example will yield 2 (1 + 1 or 3 + -1).

For your LongestSubstringKDistinct.java solution, it fails when the string has m unique characters where m < k.

The layout is very similar except that I have another map to keep track of the number of unique characters in the string. When there are less than the desired k it returns -Infinity indicating that we can never get there.

Here's my write up in javascript:

/**
 * @param {string[]} letters
 * @param {number} k
 * @returns {number} - longest substring with K distinct characters
 */
function longestSubstringWithKDistinctCharacters(letters, k) {
    let map = new Map();
    let maxLen = -Infinity;
    let uniqueCharsSeen = new Map(); // could be done with a primitive, but this was easiest
    let windowStart = 0;
    let windowEnd = 0;

    for (let i = 0; i < letters.length; i++) {
        let letter = letters[i];
        // increment windowEnd
        windowEnd++;
        // put letter in map
        map.set(letter, i);
        uniqueCharsSeen.set(letter, i);

        // adjust window when there are more distinct chars than the target
        while (map.size > k) {
            // update left side of window to the last seen index of the first item put in map
            let firstKey = map.keys().next().value;
            windowStart = map.get(firstKey) + 1; 
            // remove first char seen from the map
            map.delete(firstKey);
        }

        // update maxLen
        maxLen = Math.max(maxLen, windowEnd - windowStart);
    }

    // when string has less distinct chars than the k that are required
    if (uniqueCharsSeen.size < k) {
        return -Infinity;
    }

    return maxLen;
}

/// some test cases
console.assert(longestSubstringWithKDistinctCharacters('aaahhibc'.split(''), 2) === 5, 'aaahhibc');
console.assert(longestSubstringWithKDistinctCharacters('aaabc'.split(''), 3) === 5, 'aaabc');
// only one letter in string
console.assert(longestSubstringWithKDistinctCharacters('aaa'.split(''), 2) === -Infinity, 'aaa');

Thanks for your post, both the video and the gist were very helpful.

After reviewing your code, I realized that the while loop only does one thing. Hence, it can be replaced with an 'if'

@samuelmburu, thanks for the solution bro, I have a doubt. In your solution, should this line be in maxLen = Math.max(maxLen, windowEnd - windowStart); in a if condition map.size ===k ?

@samuelmburu while your code would solve for cases

when the string has m unique characters where m < k.

this would be a good example of when you should ask clarifying questions during the interview, such as "is it at most k distinct characters or exactly k distinct characters?"

Ideally, the spec and problem statement would cover this, but I wanted to point that out since knowing when and how to ask for clarification about the spec is a good skill to have as well as use in interviews. A lot of times, the interviews aren't specifically to see if you can solve the problem in the most optimal way, they care more about your problem-solving skills as well as how you could be as a team member.

In the real world, this is an essential skill since a majority of the time, you won't have a simple, straightforward spec sheet with everything defined and making assumptions can really harm the project.

Of course, one could take that to the extreme and require clarification on every minor detail, which isn't what you should strive for at all. I'd hate working with someone if they couldn't make decisions on their own and always took up the team's time by needing to clarify every aspect, just like I wouldn't want to work with someone who says they understand the project and then comes back a week later without asking anything and they built the wrong thing entirely.

The goal is to know what should be clearly defined (i.e deliverables, results, data, etc) versus what can be left up to interpretation. It's not obvious when starting out, but is a skill that every engineer should have though its not talked about enough which is why I felt the need to make this comment.

In LongestSubstringKDistinct solution, I think "we should update the maxLength only if the charFrequencyMap size is equals to k"

if(charFrequencyMap==k)
maxLength = Math.max(maxLength, windowEnd - windowStart + 1);