Min Window Substring

Problem

Have the function MinWindowSubstring(strArr) take the array of strings stored in strArr, which will contain only two strings, the first parameter being the string N and the second parameter being a string K of some characters, and your goal is to determine the smallest substring of N that contains all the characters in K. For example: if strArr is ["aaabaaddae", "aed"] then the smallest substring of N that contains the characters a, e, and d is "dae" located at the end of the string. So for this example your program should return the string dae.

Another example: if strArr is ["aabdccdbcacd", "aad"] then the smallest substring of N that contains all of the characters in K is "aabd" which is located at the beginning of the string. Both parameters will be strings ranging in length from 1 to 50 characters and all of K's characters will exist somewhere in the string N. Both strings will only contains lowercase alphabetic characters.

Examples

Input: ["ahffaksfajeeubsne", "jefaa"] -> Output: aksfaje
Input: ["aaffhkksemckelloe", "fhea"] -> Output: affhkkse  

What does this problem ask?

Find the shortest piece of text N that has all the letters from K hiding inside it somewhere (order doesn't matter, but count does).

["aaffhkksemckelloe", "fhea"]

If you were to illustrate this in a table, it might look something like this.

We only need the highlighted part, and that’s what we are going to code today.

So basically, we need to,

1. Create a window that checks from the left.
2. Create another window that checks from the right.

But the problem here is that you might want to have a function as well that checks whether the window already contains all the characters from ‘K’ (the comparison group), so that it can stop when it’s true.

So, let’s start coding a function that checks whether the window contains it all or not.

containsAll function

In order to do this, we’re going to make two objects containing a:num which describes the character in the window array and the string ‘K’, and num being the number of characters.

Next, we compare objectK and objectWindow: for every character in objectK, objectWindow must contain that same character with a count equal to or greater than the required amount.

The function should return a boolean depending on whether it contains all characters or not.

function containsAll (window, k) {
  const objK = {};
  for (const char of k) {
    objK[char] = (objK[char] || 0) + 1
  }

  const objWin = {};
  for (const char of window) {
    objWin[char] = (objWin[char] || 0) + 1
  }

  for (const char in objK) {
    if (!objWin[char] || objWin[char] < objK[char]) {
      return false;
    }
  }

  return true;
}

Code Explanation

• objK[char] = (objK[char] || 0) + 1
  • This code creates an object that looks something like this:
  • objK = {‘f’: 1, ‘h’:1, ‘e’:1, ‘a’:1}
  • On the first run, objK[char] becomes undefined. Therefore, you should use OR operator to put a fallback value.
• objWin[char] = (objWin[char] || 0) + 1
  • This code creates an object that looks something like this:
  • objK = {'a':2, 'f':2, 'h':1, ...}
  • On the first run, objWin[char] becomes undefined. Therefore, you should use OR operator to put a fallback value.
• if (!objWin[char] || objWin[char] < objK[char])
  • This checks whether the current character is either missing from objWin, or present in objWin with a count lower than what objK requires.

Now let’s slide the window from the left.

As you start looping from the left, checking whether the window contains all the characters from ‘K’, it should look something like the above.

To list this in an array, it should be:

let leftWin = [‘a’, ‘a’, ‘f’, ‘f’, ‘h’, ‘k’, ‘k’, ‘s’, ‘e’]

const n = "aaffhkksemckelloe";
const k = "fhea";

let leftWin = [];

for (let i=0; i < n.length; i++) {
  leftWin.push(n[i]);

  if(constainsAll(leftWin, k)) {
    break;
  }
}

This code should stop running once leftWin array has all the characters.

Now let’s slide it from the right!

For the right window, we’re not going to loop it from the ‘n’; rather, we want to start this with the leftWin array.

It should look something like above, and in an array,

let rightWin = [‘a’, ‘f’, ‘f’, ‘h’, ‘k’, ‘k’, ‘s’, ‘e’]

let rightWin = [];

for (let i = leftWin.length; i > 0; i--) {
  rightWin.push(leftWin[i]);

  if(containsAll(rightWin, k)) {
    break;
  }
}

This code should stop running once rightWin array has all the characters.

Then we return rightWin.reverse().join(‘‘); - turn it into a string, reversed.

The full code

function MinWindowSubstring(strArr) { 

  function containsAll (window, k) {
    const objK = {};

    for (const char of k) {
      objK[char] = (objK[char] || 0) + 1; 
    };

    const objWin = {};

    for (const char of window) {
      objWin[char] = (objWin[char] || 0) + 1;
    }

    for (const char in objK) {
      if (!objWin[char] || objWin[char] < objK[char]) {
        return false;
      }
    }

    return true;
  }

  const n = strArr[0];
  const k = strArr[1];

  let leftWin = [];

  for (let i = 0; i < n.length; i++) {
    leftWin.push(n[i]);

    if(containsAllleftWin, k)) {
      break;
    }
  }

  let rightWin = [];

  for (let i = rightWin.length; i > 0; i--) {
    rightWin.push(leftWin[i]);

    if(containsAll(rightWin, k)) {
      break;
    }
  }

  return windowLeft.reverse().join('');

}

console.log(MinWindowSubstring(readline()));