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));
    }
}

@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);