滑动窗口实现字符串排列检测：Solution1失效原因排查

我尝试了两种基于滑动窗口的解法，其中一种参考了网络资源。Solution1在特定输入下无法得到正确结果：输入s1="trinitrophenylmethylnitramine"、s2="dinitrophenylhydrazinetrinitrophenylmethylnitramine"时，预期返回true但实际返回false，而Solution2能正常返回true，以下是对Solution1失效点的分析：

Solution 1 代码 #

var checkInclusion = function(s1, s2) {
  if (s1.length > s2.length) {
    return false;
  }

  const freqMap = {};
  let count = 0;
  let start = 0;
  let end = 0;

  for (let char of s1) {
    if (freqMap[char] === undefined) count++;
    freqMap[char] = (freqMap[char] || 0) + 1;
  }

  while (s2.length > end) {
    let nextChar = s2[end];

    if (freqMap[nextChar] !== undefined) {
      freqMap[nextChar]--;
      if (freqMap[nextChar] === 0) {
        count--;
      }
    }

    end++;
    if (count === 0) {
      return true;
    }

    if (end - start === s1.length) {
      let temp = s2[start];
      if (freqMap[temp] !== undefined) {
        freqMap[temp] += 1;
        if (freqMap[temp] > 0) count++;
      }
      start++;
    }
  }
  return false;
};

const s1 = "trinitrophenylmethylnitramine";
const s2 = "dinitrophenylhydrazinetrinitrophenylmethylnitramine";
console.log(checkInclusion(s1, s2));

Solution 2 代码 #

var checkInclusion_1 = function(s1, s2) {
  if (s1.length > s2.length) return false;
  let neededChar = {};
  for (let i = 0; i < s1.length; i++) {
    neededChar[s1[i]] = (neededChar[s1[i]] || 0) + 1;
  }

  let left = 0, //left pointer/index of the sliding window
    right = 0, //right pointer/index of the sliding window
    requiredLength = s1.length; //length of the substring required in s2

  // Now iterate until the right index of window is lesser than length of s2
  while (right < s2.length) {
    // If we found s2 character in s1 i.e in neededChar then we decrease requiredLength
    if (neededChar[s2[right]] > 0) requiredLength--;
    // Since we have encountered new char i.e s2[right] we decrease it's
    // count in neededChar even if it is not present in neededChar because we only care about neededChars
    neededChar[s2[right]]--;
    right++; //window is incremented by 1 step

    // Now if our requiredLength becomes 0 it means we have found a match of the s2 substring
    // So we return true
    if (requiredLength === 0) return true;

    // If our window length is equal to s1 length (length of string to search in s2)
    // then we have to remove left element of window i.e left++ and add new element from right
    // will be added in next iteration
    if (right - left === s1.length) {
      // if the left element we are removing was a required character then we increase requiredLength
      // because that element will no longer be the part of sliding window
      if (neededChar[s2[left]] >= 0) requiredLength++;
      // We will also increase the count of left element removed from window
      neededChar[s2[left]]++;

      left++;
    }
  }
  // If match was not found we return false
  return false;
};

const s1 = "trinitrophenylmethylnitramine";
const s2 = "dinitrophenylhydrazinetrinitrophenylmethylnitramine";
console.log(checkInclusion_1(s1, s2));

Solution1 失效原因分析 #

两个解法的核心差异在于匹配状态的跟踪方式：

• Solution1用count变量跟踪还未满足频率要求的不同字符数量，只有当所有字符的频率都刚好匹配（freqMap[char] === 0）时，count才会变为0并返回true。
• Solution2用requiredLength变量跟踪还未匹配的字符总数，只要窗口内的字符总数刚好覆盖s1的所有字符（即使中间有超额字符，也不会错误减少计数），就能正确触发返回。

Solution1的致命问题在于：
当s2的前缀部分包含大量s1中的字符（出现次数超过s1中的对应次数）时，freqMap中这些字符的数值会变为负数。后续窗口滑动到s1的完整排列位置时，freqMap的数值无法回到0：

1. 前缀的超额字符会让freqMap[char]持续减少（比如s1中某字符出现3次，前缀出现5次，freqMap[char]会变为3-5=-2）。
2. 当窗口滑动到正确排列时，每个进入窗口的该字符会继续减少freqMap[char]，而移出窗口的前缀字符会增加freqMap[char]，最终freqMap[char]的数值等于前缀中该字符的剩余数量（正数）。
3. 此时该字符的freqMap值大于0，会被计入count，导致count无法降到0，程序无法识别到正确的排列，最终返回false。

而Solution2的requiredLength只会在字符的剩余需求大于0时才减少计数，超额字符不会影响总计数；窗口滑动时也只会恢复被错误减少的计数，因此能准确识别出正确的排列。

内容的提问来源于stack exchange，提问作者Zeeshan Ali