1

I am given a string and an array of single character strings as an argument. I need to return the shortest substring that can be found in the given string that contains every character in the array.

I am assuming that all characters are lower case and that the substring will be at least two characters long.

This is how I have it set up:

const solve = (strArg, charArray) => {
  let result = '';
  const strArray = strArg.split('');
  return;
}

solve("environmental earth science", ["n","e","i","m"]);

I want to loop over the strArg and say does this letter exist in the charArray, but I want to use an ES6 array helper method and I have looked at filter(), but if I look at how T.J Crowder defines the use of filter(), that is more for creating a new array.

So then I have also looked at the for..of loop, but I am unclear as to whether I am applying it wrong or the for..of is not the best for the job. I need to iterate over each character in strArray and see if it exists in charArray.

halfer
  • 19,824
  • 17
  • 99
  • 186
Daniel
  • 14,004
  • 16
  • 96
  • 156

1 Answers1

1

A brute-force solution would be to start at each index of the input string, then increment indicies until all required characters have been found. Do this starting at index 0, then at index 1, etc.

const solve = (str, charArray) => {
  let bestStr = str;
  for (let i = 0; i < str.length; i++) {
    const chars = new Set(charArray);
    for (let j = i; j < str.length; j++) {
      chars.delete(str[j]);
      const thisLen = j - i + 1;
      if (chars.size === 0 && bestStr.length > thisLen) {
        bestStr = str.slice(i, j + 1);
        break;
      }
    }
  }
  return bestStr;
}

console.log(solve("environmental earth science", ["n","e","i","m"]));

I don't think filter is very useful here, because constructing an intermediate array doesn't lead to accomplishing anything useful as far as I can see. for..of, while it looks cleaner, doesn't keep track of indicies as well as a plain for loop.

CertainPerformance
  • 356,069
  • 52
  • 309
  • 320
  • I had heard about this brute force solution but I thought maybe that was not the ideal solution. Thank you. – Daniel Mar 19 '20 at 04:01
  • It's a solution to the problem in your question, which is probably a lot better than not knowing where to start. If `O(n ^ 2)` solutions are not permitted, probably best to edit your question to specify such – CertainPerformance Mar 19 '20 at 04:08
  • shouldn't the output be `nme` instead of `ironme` in this case? – shrys Mar 19 '20 at 04:09
  • 1
    @shrys That doesn't contain every letter of the `charArray` argument, so it wouldn't be a solution, right? *return the shortest substring that can be found in the given string that contains every character in the array.* – CertainPerformance Mar 19 '20 at 04:10
  • @CertainPerformance, thanks again. I was not criticizing your answer, its a new problem for me and when I saw "brute force" on some websites, it sounded hacky, but what did I know? – Daniel Mar 19 '20 at 04:37
  • @CertainPerformance, And thanks for exposing me to the `Set` object. – Daniel Mar 19 '20 at 04:52