HashMap Frequence
Create the function MinWindowSubstring(strArr), which takes in an array containing two strings. The first string, N, is a longer string, and the second string, K, consists of a set of characters. Your task is to find the smallest substring of N that contains all the characters in K.
For example, if the input is ["aaabaaddae", "aed"], the smallest substring in N that contains the characters ‘a’, ‘e’, and ‘d’ is "dae", which appears at the end of N. So the output should be "dae".
Another example: if the input is ["aabdccdbcacd", "aad"], the smallest substring that contains all the characters in K is "aabd", which is at the start of N.
The strings in strArr will range from 1 to 50 characters in length. The string K will always have its characters somewhere within N, and both strings will only contain lowercase alphabetic letters.
Example inputs:
- Input:
["ahffaksfajeeubsne", "jefaa"]
Output:"aksfaje" - Input:
["aaffhkksemckelloe", "fhea"]
Output:"affhkkse"
public static String minWindowSubstring(String[] strArr) {
String N = strArr[0]; // The longer string
String K = strArr[1]; // The characters to be matched
// Base case check
if (N.length() == 0 || K.length() == 0) return "";
// Frequency map for characters in K
HashMap<Character, Integer> targetMap = new HashMap<>();
for (char c : K.toCharArray()) {
targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
}
// Sliding window pointers
int left = 0, right = 0;
int minLen = Integer.MAX_VALUE; // Minimum length of the substring
int start = 0; // Start position of the smallest window
int matchedChars = 0; // To keep track of matched characters
// Map to keep track of the characters in the current window
HashMap<Character, Integer> windowMap = new HashMap<>();
while (right < N.length()) {
// Expand the window by including the current character at 'right'
char rightChar = N.charAt(right);
if (targetMap.containsKey(rightChar)) {
windowMap.put(rightChar, windowMap.getOrDefault(rightChar, 0) + 1);
// Count the matched characters
if (windowMap.get(rightChar).intValue() == targetMap.get(rightChar).intValue()) {
matchedChars++;
}
}
// Shrink the window if all characters are matched
while (matchedChars == targetMap.size()) {
// Update the minimum window size
if (right - left + 1 < minLen) {
minLen = right - left + 1;
start = left;
}
// Shrink the window by moving 'left' pointer
char leftChar = N.charAt(left);
if (targetMap.containsKey(leftChar)) {
windowMap.put(leftChar, windowMap.get(leftChar) - 1);
if (windowMap.get(leftChar) < targetMap.get(leftChar)) {
matchedChars--;
}
}
left++;
}
// Move the 'right' pointer to the next position
right++;
}
// Return the smallest window, or an empty string if no valid window was found
return minLen == Integer.MAX_VALUE ? "" : N.substring(start, start + minLen);
}
