0
\$\begingroup\$

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);
}


console.log(minimumWindowSubstring("ADOBECODEBANC", "ABC")) //  "BANC"
\$\endgroup\$
  • 2
    \$\begingroup\$ What is n in the complexity O(n)? Length of S? length of T? size of an alphabet? \$\endgroup\$ – vnp Jul 30 '18 at 20:49
  • \$\begingroup\$ This is \$O(n^2+n)\$ complexity... I think. \$\endgroup\$ – FreezePhoenix Jul 30 '18 at 21:20
  • \$\begingroup\$ yes. O(n^2) solution. \$\endgroup\$ – NinjaG Aug 2 '18 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.