各位题友大家好，今天是每日算法题公众号坚持日更的第 17 天。今天力扣上的每日一题是「567. 字符串的排列」。

题目大意

示例

数据范围

解题思路

滑动窗口 + 字典

题目要求 s1 的排列之一是 s2 的一个子串。而子串必须是连续的，所以要求的 s2 子串的长度跟 s1 长度必须相等。

那么我们有必要把 s1 的每个排列都求出来吗？当然不用。如果字符串 a 是 b 的一个排列，那么当且仅当它们两者中的每个字符的个数都必须完全相等。

所以，根据上面两点分析，我们已经能确定这个题目可以使用 滑动窗口 + 字典 来解决。

我们使用一个长度和 s1 长度相等的固定窗口大小的滑动窗口，在 s2 上面从左向右滑动，判断 s2 在滑动窗口内的每个字符出现的个数是否跟 s1 每个字符出现次数完全相等。

我们定义 counter1 是对 s1 内字符出现的个数的统计，定义 counter2 是对 s2 内字符出现的个数的统计。在窗口每次右移的时候，需要把右边新加入窗口的字符个数在 counter2 中加 1，把左边移出窗口的字符的个数减 1。如果 counter1 == counter2 ，那么说明窗口内的子串是 s1 的一个排列，返回 True；如果窗口已经把 s2 遍历完了仍然没有找到满足条件的排列，返回 False。

躲坑指南：

  1. 本题中的 counter 可以用字典，也可以用数组来实现。用字典的时候，需要注意：如果移除 left 元素后，若 counter2[s2[left]] == 0 那么需要从字典中删除 left 这个key。因为 {"a":0, "b":1} 和 {"b":1} 是不等的。
  2. 窗口的定义一定要搞清楚是否包含两边的端点，比如我定义的窗口是 [left, right] 两个端点都包含，那么就需要把两个端点的元素也放入 counter2 中。
  3. counter2 初始化的时候只放了 [0, right - 1] 个元素，因为在 while 循环中的第一行就是把 right 元素放到 counter2 中。

代码

使用 Python2 写的代码如下。注释超详细，其他语言可以对应修改。

  1. class Solution(object):
  2.     def checkInclusion(self, s1, s2):
  3.         """
  4.         :type s1: str
  5.         :type s2: str
  6.         :rtype: bool
  7.         """
  8.         # 统计 s1 中每个字符出现的次数
  9.         counter1 = collections.Counter(s1)
  10.         N = len(s2)
  11.         # 定义滑动窗口的范围是 [left, right]，闭区间，长度与s1相等
  12.         left = 0
  13.         right = len(s1) - 1
  14.         # 统计窗口s2[left, right - 1]内的元素出现的次数
  15.         counter2 = collections.Counter(s2[0:right])
  16.         while right < N:
  17.             # 把 right 位置的元素放到 counter2 中
  18.             counter2[s2[right]] += 1
  19.             # 如果滑动窗口内各个元素出现的次数跟 s1 的元素出现次数完全一致，返回 True
  20.             if counter1 == counter2:
  21.                 return True
  22.             # 窗口向右移动前，把当前 left 位置的元素出现次数 - 1
  23.             counter2[s2[left]] -= 1
  24.             # 如果当前 left 位置的元素出现次数为 0， 需要从字典中删除，否则这个出现次数为 0 的元素会影响两 counter 之间的比较
  25.             if counter2[s2[left]] == 0:
  26.                 del counter2[s2[left]]
  27.             # 窗口向右移动
  28.             left += 1
  29.             right += 1
  30.         return False

刷题心得

今天这个题不难，是常规的固定窗口大小的滑动窗口问题。但是细节比较多，比如 counter2 初始化放多少个元素；当移除 left 指向元素的时候，如果此时该元素个数为 0，需要从字典中删除 key 等。

参考资料：
1. 力扣官方题解：字符串的排列
2. 负雪明烛博客：567. Permutation in String
3. 【LeetCode】代码模板，刷题必会

欢迎加入刷题群

目前已经近 2000 人加入了每日一题打卡群。加入方式是通过每日一题打卡网站。每天都会同步力扣每日一题，这是个互相帮助、互相监督的算法题打卡网站，其地址是 https://www.ojeveryday.com/
【每日一题】567. 字符串的排列 - 图1

想加入千人刷题群的朋友，可以复制上面的链接到浏览器，然后在左侧点击「加入组织」，提交力扣个人主页，即可进入刷题群。期待你早日加入。

也可点击 「阅读原文」，直接提交力扣个人主页。

关于作者

我是本文的作者是负雪明烛，毕业于北京邮电大学，目前就职于阿里巴巴。坚持刷算法题 5 年，共计刷了 800 多道算法题。做过的每个算法题都在 CSDN 上写题解博客，获得好评无数，CSDN 的累计阅读量已经 160万 次！博客地址是：https://blog.csdn.net/fuxuemingzhu
「每日算法题」公众号是我维护的一个算法题解公众号，主要讲解算法题的解法，也会分享找工作的经验。欢迎关注。
【每日一题】567. 字符串的排列 - 图2

题目来源：839. 相似字符串组https://leetcode-cn.com/problems/similar-string-groups/