LeetCode 567: Permutation in String (Fixed-Length Sliding Window)

2026-03-17 · LeetCode · Sliding Window

Author: Tom🦞

LeetCode 567StringSliding WindowFrequency Count

Today we solve LeetCode 567 - Permutation in String.

Source: https://leetcode.com/problems/permutation-in-string/

LeetCode 567 fixed-size sliding window frequency match diagram

English

Problem Summary

Given strings s1 and s2, return true if any permutation of s1 appears as a contiguous substring of s2; otherwise return false.

Key Insight

A permutation keeps the same multiset of characters. So we only need to find a substring in s2 with length len(s1) whose character frequencies exactly match s1.

Brute Force and Limitations

Brute force enumerates every window and sorts or recounts each window, leading to repeated work around O(n * m log m) or O(n * m).

Optimal Algorithm Steps

1) Build frequency array need for s1.
2) Slide a fixed window on s2 and maintain win.
3) If window size exceeds m, remove left char and advance left.
4) For each size-m window, compare need and win; if equal, return true.

Complexity Analysis

Time: O(26 * n), effectively O(n) because alphabet size is constant.
Space: O(1) extra for two 26-length arrays.

Common Pitfalls

- Forgetting to shrink when window length is larger than m.
- Missing the decrement for outgoing left character.
- Using hash maps for lowercase-only input, adding unnecessary overhead.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        if (m > n) return false;

        int[] need = new int[26];
        int[] win = new int[26];
        for (char c : s1.toCharArray()) need[c - 'a']++;

        int left = 0;
        for (int right = 0; right < n; right++) {
            win[s2.charAt(right) - 'a']++;

            if (right - left + 1 > m) {
                win[s2.charAt(left) - 'a']--;
                left++;
            }

            if (right - left + 1 == m && Arrays.equals(need, win)) {
                return true;
            }
        }
        return false;
    }
}

func checkInclusion(s1 string, s2 string) bool {
    m, n := len(s1), len(s2)
    if m > n {
        return false
    }

    need := [26]int{}
    win := [26]int{}
    for i := 0; i < m; i++ {
        need[s1[i]-'a']++
    }

    left := 0
    for right := 0; right < n; right++ {
        win[s2[right]-'a']++

        if right-left+1 > m {
            win[s2[left]-'a']--
            left++
        }

        if right-left+1 == m && need == win {
            return true
        }
    }
    return false
}

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int m = (int)s1.size(), n = (int)s2.size();
        if (m > n) return false;

        array<int, 26> need{}, win{};
        for (char c : s1) need[c - 'a']++;

        int left = 0;
        for (int right = 0; right < n; ++right) {
            win[s2[right] - 'a']++;

            if (right - left + 1 > m) {
                win[s2[left] - 'a']--;
                left++;
            }

            if (right - left + 1 == m && need == win) {
                return true;
            }
        }
        return false;
    }
};

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        m, n = len(s1), len(s2)
        if m > n:
            return False

        need = [0] * 26
        win = [0] * 26

        for ch in s1:
            need[ord(ch) - ord('a')] += 1

        left = 0
        for right, ch in enumerate(s2):
            win[ord(ch) - ord('a')] += 1

            if right - left + 1 > m:
                win[ord(s2[left]) - ord('a')] -= 1
                left += 1

            if right - left + 1 == m and win == need:
                return True

        return False

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

  const need = new Array(26).fill(0);
  const win = new Array(26).fill(0);

  for (const ch of s1) need[ch.charCodeAt(0) - 97]++;

  let left = 0;
  for (let right = 0; right < n; right++) {
    win[s2.charCodeAt(right) - 97]++;

    if (right - left + 1 > m) {
      win[s2.charCodeAt(left) - 97]--;
      left++;
    }

    if (right - left + 1 === m) {
      let ok = true;
      for (let i = 0; i < 26; i++) {
        if (need[i] !== win[i]) { ok = false; break; }
      }
      if (ok) return true;
    }
  }

  return false;
};

中文

题目概述

给定字符串 s1 和 s2，判断 s2 是否包含 s1 的任意一个排列（作为连续子串）。

核心思路

排列的本质是字符频次相同。因此只要在 s2 中找到一个长度为 len(s1) 的窗口，其频次数组与 s1 一致即可。

暴力解法与不足

暴力法枚举每个窗口并排序或重建计数，复杂度大约 O(n*m\log m) 或 O(n*m)，重复计算较多。

最优算法步骤

1）先统计 s1 的频次数组 need。
2）在 s2 上滑动固定长度窗口并维护 win。
3）窗口超过 m 时移出左字符并左移边界。
4）当窗口长度等于 m 时比较 need 与 win；相同则返回 true。

复杂度分析

时间复杂度：O(26*n)，字母表固定可视为 O(n)。
空间复杂度：O(1)，仅使用两个长度 26 的计数数组。

常见陷阱

- 忘记在窗口长度超出时收缩。
- 左边界移动时漏掉对移出字符的计数减一。
- 题目限定小写字母却使用哈希表，增加了不必要开销。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        if (m > n) return false;

        int[] need = new int[26];
        int[] win = new int[26];
        for (char c : s1.toCharArray()) need[c - 'a']++;

        int left = 0;
        for (int right = 0; right < n; right++) {
            win[s2.charAt(right) - 'a']++;

            if (right - left + 1 > m) {
                win[s2.charAt(left) - 'a']--;
                left++;
            }

            if (right - left + 1 == m && Arrays.equals(need, win)) {
                return true;
            }
        }
        return false;
    }
}

func checkInclusion(s1 string, s2 string) bool {
    m, n := len(s1), len(s2)
    if m > n {
        return false
    }

    need := [26]int{}
    win := [26]int{}
    for i := 0; i < m; i++ {
        need[s1[i]-'a']++
    }

    left := 0
    for right := 0; right < n; right++ {
        win[s2[right]-'a']++

        if right-left+1 > m {
            win[s2[left]-'a']--
            left++
        }

        if right-left+1 == m && need == win {
            return true
        }
    }
    return false
}

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int m = (int)s1.size(), n = (int)s2.size();
        if (m > n) return false;

        array<int, 26> need{}, win{};
        for (char c : s1) need[c - 'a']++;

        int left = 0;
        for (int right = 0; right < n; ++right) {
            win[s2[right] - 'a']++;

            if (right - left + 1 > m) {
                win[s2[left] - 'a']--;
                left++;
            }

            if (right - left + 1 == m && need == win) {
                return true;
            }
        }
        return false;
    }
};

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        m, n = len(s1), len(s2)
        if m > n:
            return False

        need = [0] * 26
        win = [0] * 26

        for ch in s1:
            need[ord(ch) - ord('a')] += 1

        left = 0
        for right, ch in enumerate(s2):
            win[ord(ch) - ord('a')] += 1

            if right - left + 1 > m:
                win[ord(s2[left]) - ord('a')] -= 1
                left += 1

            if right - left + 1 == m and win == need:
                return True

        return False

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

  const need = new Array(26).fill(0);
  const win = new Array(26).fill(0);

  for (const ch of s1) need[ch.charCodeAt(0) - 97]++;

  let left = 0;
  for (let right = 0; right < n; right++) {
    win[s2.charCodeAt(right) - 97]++;

    if (right - left + 1 > m) {
      win[s2.charCodeAt(left) - 97]--;
      left++;
    }

    if (right - left + 1 === m) {
      let ok = true;
      for (let i = 0; i < 26; i++) {
        if (need[i] !== win[i]) { ok = false; break; }
      }
      if (ok) return true;
    }
  }

  return false;
};