This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

52. Minimum Coverage substring (minimum-window-substring)

The label

  • The sliding window
  • difficult

The title

Leetcode portal

Let’s just open leetCode.

I give you a string S, a string t. Returns the smallest string in S that covers all characters of t. Return an empty string “” if there is no substring in S that covers all characters of t.

Note: if such a substring exists in S, we guarantee that it is the only answer.

The sample

Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Example 2: Input: s = "a", t = "a" Output: "a"Copy the code

The basic idea

The typical sliding window idea, if not, please move on to the third question in this article:

Sliding window idea

So this problem can be understood as: ask to find a minimum window in S, this window contains all the characters in T. Returns an empty string if none exists.

Basic steps

  1. We first need to determine the condition that the sliding window meets: the windowsubstringContained withintAll of the characters of, note that there may be repeated characters, so you can’t use sort or other rough solutions, so let’s just
    • Create a Map,keyRepresents the character,valueIt’s the number of occurrences liket = ABCC= >Map { 'A' => 1, 'B' => 1, 'C' => 2 }
    • Use curLessKeysLen to indicate the type of characters that remain to be matched
    • So the conditions that are satisfied arecurLessKeysLen === 0That means everything matches, which is equal toneedMap = { 'A' => 0, 'B' => 0, 'C' => 0 }
  2. Slide the right pointer to enlarge the window(right++), until the condition is met, the comparison is recordedThe optimal solution.
  3. At this point, we stop adding right and keep adding rightleftPointer narrowing window[left, right]Until the string in the window no longer meets the requirementscurLessKeysLen > 0. Also, each time we add a left, we update the result of a round.
  4. Repeat steps 2 and 3 untilrightArrival stringsIn the end.

Writing implement

var minWindow = function(s, t) {
  // Declare result string, left and right pointer, original length
  let [res, left, right, len] = ["".0.0, s.length]
  // Declare the dictionary mapping table
  let needMap = new Map(a)// Fill in the current dictionary table according to t assuming t = "ABCC"
  t.split(' ').map(item= > {
    if (needMap.has(item)) {
      needMap.set(item, needMap.get(item) + 1)}else {
      needMap.set(item, 1)}})// console.log(needMap)
  // Map { 'A' => 1, 'B' => 1, 'C' => 2 }
  // Type of characters that still need to be matched
  let curLessKeysLen = needMap.size;
  // Start window sliding
  while (right < len) {
    let curR = s[right]
    if (needMap.has(curR)) {
      // include the window with needMap corresponding element -1
      needMap.set(curR, needMap.get(curR) - 1)
      // The corresponding element is satisfied
      if (needMap.get(curR) === 0) {
        curLessKeysLen -= 1; }}// If the remaining matching length is 0, the current window meets the requirements
    while (curLessKeysLen === 0) {
      let curL = s[left]
      let nowStr = s.slice(left, right + 1);
      // Make a note of the current requirements and the shortest
      if (res === "" || res.length > nowStr.length) {
        res = nowStr
      }
      // Now it is time to move the left border, and of course needMap should change with it
      if (needMap.has(curL)) {
        needMap.set(curL, needMap.get(curL) + 1)
        if (needMap.get(curL) === 1) {
          curLessKeysLen += 1;
        }
      }
      left++;
    }
    right++;
  }
  return res
};

let s = "ADOBECODEBANC", t = "ABC"
console.log(minWindow(s, t))
Copy the code

In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me presious tower shock the rever monster, I see it through, the code is not on the ha, add after I will do my best to help you, but pay attention to the way of asking questions, suggest reading this article first: the wisdom of asking questions

reference