Return the shortest substring containing all the characters in the set

Question

The task:

Given a string and a set of characters, return the shortest substring containing all the characters in the set.

For example, given the string "figehaeci" and the set of characters {a, e, i}, you should return "aeci".

If there is no substring containing all the characters in the set, return null.

My solution:

// init
const originalStr = 'figehaeci';
const set = Object.freeze(['a', 'e', 'i']);
// helpers
const isEmpty = s => s.length === 0;
const copy = s => s.slice(0);
const getNextResult = (currRes, endRes) => {
 if (!endRes || isEmpty(endRes)) {
 return currRes;
 }
 return currRes.length < endRes.length ?
 currRes : endRes;
};
// main
const contains = (str, endResult) => {
 const currStr = str;
 const currSet = copy(set);
 let pushIt;
 const currResult = currStr
 .split('')
 .reduce((acc, item) => {
 if (pushIt === false) {
 return acc;
 }
 if (currSet.includes(item)) {
 currSet.splice(currSet.indexOf(item), 1);
 pushIt = true;
 }
 if (pushIt) {
 acc.push(item);
 }
 if (isEmpty(currSet)) {
 pushIt = false;
 }
 return acc;
 }, []);
 const nextStr = str
 .split('')
 .slice(1)
 .join('');
 // exit case
 if (isEmpty(nextStr)) {
 return endResult ? endResult.join('') : null;
 }
 // recursive case
 const nextResult = isEmpty(currSet) ?
 getNextResult(currResult, endResult) :
 endResult;
 return contains(nextStr, nextResult);
}
// result
console.log(contains(originalStr, null));

I don't like the many ifs and the flag (pushIt). Do you know how to get rid of them without sacrificing readability and maintainability?

Doesn't have to be in functional programming style. Just looking for an elegant solution.

Answer 1

Too complex

Your complexity is very high. My guess is between \$O(n^2)\$ and \$O(n^3)\$. I can think of a \$O(nLog(n))\$ solutions and there is likely a \$O(n)\$ solution.

You are very wasteful of CPU cycles, some example follow...

String don't need to be arrays to manipulate.

const nextStr = str.split('').slice(1).join(''); // cost O(3n-2) n = str.length
// Can be O(n-1)
const nextStr = str.substring(1);

Don't add code not needed.

currStr = str // cost O(n) n = str.length
// Can be O(0) as you don't need to copy it

Don't repeat operations.

if (currSet.includes(item)) { currSet.splice(currSet.indexOf(item), 1) // cost O(2n) 
 // n = currSet.length
// Can be O(n)
const idx = currSet.indexOf(item);
if (idx > -1) { currSet.splice(idx, 1) }

Strings

When you copy a string the computer must step over every character. Unlike many languages in JS strings are not passed by reference, they are copied, thus passing a string to a function will have a complexity cost that matches the string length. You should avoid making copies of strings whenever you can.

Fast search with Set and Map

Use Sets and Maps. They create hash tables (cost \$O(n)\$) that make finding items very fast \$O(1)\$.

Optimise and use information you have

Check for opportunities to exit the function early. Eg if the remain characters to search is less than the number of characters in the set there is no need to search. If you find a match that is the same length as the set you dont need to search further. If the set is longer than the string to search you don't need to do the search.

---

Use appropriate language features.

• Copy arrays with [...array] not array.slice(0)
• Iterate strings without splitting for(const char of "A string of chars") {...

Example

This uses Set to make locating matching character quick. If a match is found another set is used to count off characters as they are found. This gives you a complexity of around \$O(nLog(n))\$

It returns an empty string if nothing is found and it avoids copying string.

I have a feeling that there is an \$O(n)\$ solution but your question does not clearly define the problem and thus I will not invest any more time as it may all be for naught.

function shortestSubStrContaining(str, chars){
 const charSet = new Set(chars);
 if (str.length < chars.length) { return "" }
 var i = 0, start, minSize = str.length;
 done: while (i < str.length) {
 if (charSet.has(str[i])) {
 const check = new Set(chars);
 check.delete(str[i]);
 let j = i + 1;
 while (j < str.length) {
 if (check.has(str[j])) {
 check.delete(str[j]);
 if (check.size === 0) {
 if (j - i < minSize) {
 minSize = j - i + 1;
 start = i;
 if (minSize === chars.length || str.length - (i + 1) < minSize ) { 
 break done;
 }
 }
 }
 }
 j++
 }
 }
 i++;
 if (str.length - i < chars.length) { break }
 }
 return str.substring(start, start + minSize); // if start undefined will return "" 
} 

• thadeuszlay: You opened my eyes. I wish I could upvote more than once.
• thadeuszlay: What is done exactly doing? How do you call it? Never seen that before done: while (i < str.length) {
• thadeuszlay: I found it: Labled statement developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
• thadeuszlay: There are some inefficiency in my code, I totally agree with you. But how would you rate the readability of your code in comparison to mine?
• Blindman67: @thadeuszlay You have a function called contains that gives nothing away. The helper functions copy(copy what?), isEmpty (is what empty) and getNextResult (get next result for what) are isolated and outside the calling function and also give no clue as to what they are for and why. If I found that in a sea of code I would be left guessing. If I found shortestSubStrContaining(str, chars){ I would not have to read another line to know what it does. Readability is how an experienced proficient coder outside the problem sees the code, not the author

Answer 2

I couldn't remove the ifs and the flag , so i thought about a diffrent aproach,

Using regular expressions seem more reasonable aproach, you can have a function that returns all the possible combinations of the letters in the array, create regular expressions from the resulting combinations and match against the orignalStr,

function perm(xs) {
 let ret = [];
 for (let i = 0; i < xs.length; i = i + 1) {
 let rest = perm(xs.slice(0, i).concat(xs.slice(i + 1)));
 if (!rest.length)
 ret.push([xs[i]]);
 else
 for (let j = 0; j < rest.length; j = j + 1)
 ret.push([xs[i]].concat(rest[j]));
 }
 return ret;
}
const originalStr = 'figehaeci', letters = ['a', 'e', 'i'];
let result = originalStr;
const combinations = perm(letters).map(combo => combo.join('.*?'));
// combinations : ["a.*?e.*?i","a.*?i.*?e","e.*?a.*?i","e.*?i.*?a","i.*?a.*?e","i.*?e.*?a"]
combinations.forEach(combo => {
 const exp = new RegExp(combo, 'g');
 const matches = originalStr.match(exp) || [];
 matches.forEach(match => {
 if (match.length <= result.length)
 result = match;
 });
});
console.log(result);

The code you posted returns only one value if there's more substrings containing those letters, here's a tweak to store all possible shortest combinations in an array :

function perm(xs) {
 let ret = [];
 for (let i = 0; i < xs.length; i = i + 1) {
 let rest = perm(xs.slice(0, i).concat(xs.slice(i + 1)));
 if (!rest.length)
 ret.push([xs[i]]);
 else
 for (let j = 0; j < rest.length; j = j + 1)
 ret.push([xs[i]].concat(rest[j]));
 }
 return ret;
}
const originalStr = 'figehaecizaexi', letters = ['a', 'e', 'i'];
let shortestLength = originalStr.length, result = [];
const combinations = perm(letters).map(combo => combo.join('.*?'));
// combinations : ["a.*?e.*?i","a.*?i.*?e","e.*?a.*?i","e.*?i.*?a","i.*?a.*?e","i.*?e.*?a"]
combinations.forEach(combo => {
 const exp = new RegExp(combo, 'g');
 const matches = originalStr.match(exp) || [];
 matches.forEach(match => {
 if (match.length < shortestLength) {
 shortestLength = match.length;
 result = [match];
 }
 if (match.length === shortestLength) {
 result.push(match);
 }
 });
});
const deduped = [...new Set(result)];
console.log(deduped);

• thadeuszlay: I haven't thought about this approach. Really interesting!