# Minimum Window Substring in JavaScript

I find this Substring Leetcode challenge online. Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity $O(n^2)$ or $O(n)$ (optimized).

Input: S = "ADOBECODEBANC", T = "ABC"

Output: "BANC"

I did the following approach. Moving Window problems. I also test my code on repl.it.

function minimumWindowSubstring(S, T) {

let result = [0, Infinity]
let counts = {};
let missingCharacters = T.length;

//   Create the counts hash table
for(let i = 0; i < T.length; i++) {
counts[T[i]] = 0;
}

let slow = 0;

for(let fast = 0; fast < S.length; fast++) {

//     Check if character at fast index is incounts hash
if(S[fast] in counts) {

//     If you haven't seen that character before
if(counts[S[fast]] === 0) {

//         Decrement number of missing characters
missingCharacters -= 1;
}

//       And add one to its counts value
counts[S[fast]] += 1
}

//     Shrink window until you have an incomplete set
while(missingCharacters === 0) {

//       Updates result range if smaller than previous range
if((fast - slow) < (result[1] - result[0])) {
result[0] = slow
result[1] = fast
}

if(S[slow] in counts) {
counts[S[slow]] -= 1
if(counts[S[slow]] === 0) {
missingCharacters += 1
}
}
slow += 1;
}
}

return result[1] === Infinity ? "" : S.slice(result[0], result[1] + 1);
}


• What is n in the complexity O(n)? Length of S? length of T? size of an alphabet? – vnp Jul 30 '18 at 20:49
• This is $O(n^2+n)$ complexity... I think. – FreezePhoenix Jul 30 '18 at 21:20