各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 34 天。今天力扣上的每日一题是「395. 至少有K个重复字符的最长子串」。

解题思路

本题要求的一个最长的子字符串的长度，该子字符串中每个字符出现的次数都最少为 $k$。

求最长子字符串/区间的这类题一般可以用滑动窗口来做，但是本题滑动窗口的代码不好写，我改用递归。也借本题来帮助大家理解递归。

递归最重要的是记住递归函数的含义：本题的 longestSubstring(s, k) 函数表示的就是题意，即求一个最长的子字符串的长度，该子字符串中每个字符出现的次数都最少为 $k$。函数入参 $s$ 是表示源字符串；$k$ 是限制条件，即子字符串中每个字符最少出现的次数；函数返回结果是满足题意的最长子字符串长度。（有点啰嗦，但是务必牢记函数的定义）

我们在调用递归函数的时候，把递归函数当做普通函数（黑箱）来调用，即明白该函数的输入输出是什么，而不用管此函数内部在做什么。

递归的终止条件（能直接写出的最简单 case）：如果字符串 $s$ 的长度少于 $k$，那么一定不存在满足题意的子字符串，返回 0；

调用递归（重点）：如果一个字符 $c$ 在 $s$ 中出现的次数少于 $k$ 次，那么 $s$ 中所有的包含 $c$ 的子字符串都不能满足题意。所以，应该在 $s$ 的所有不包含 $c$ 的子字符串中继续寻找结果：把 $s$ 按照 $c$ 分割（分割后每个子串都不包含 $c$），得到很多子字符串 $t$；下一步要求 $t$ 作为源字符串的时候，它的最长的满足题意的子字符串长度（到现在为止，我们把大问题分割为了小问题($s$ → $t$)）。此时我们发现，恰好已经定义了函数 longestSubstring(s, k) 就是来解决这个问题的！所以直接把 longestSubstring(s, k) 函数拿来用，于是形成了递归。

默认返回结果：如果 $s$ 中的每个字符出现的次数都大于 $k$ 次，那么 $s$ 就是我们要求的字符串，直接返回该字符串的长度。

通过上面的分析，我们看出了：我们不是为了递归而递归。而是因为我们把大问题拆解成了小问题，恰好有函数可以解决小问题，所以直接用这个函数。由于这个函数正好是本身，所以我们把此现象叫做递归。小问题是原因，递归是结果。而递归函数到底怎么一层层展开与终止的，不要用大脑去想，这是计算机干的事。我们只用把递归函数当做一个能解决问题的黑箱就够了，把更多的注意力放在拆解子问题、递归终止条件、递归函数的正确性上来。

希望我说的这些能对你理解递归有所帮助。

代码

  1. class Solution(object):
  2.     def longestSubstring(self, s, k):
  3.         if len(s) < k:
  4.             return 0
  5.         for c in set(s):
  6.             if s.count(c) < k:
  7.                 return max(self.longestSubstring(t, k) for t in s.split(c))
  8.         return len(s)
  • 时间复杂度：$O(n^2)$，因为for循环一次，循环里面对$s$分割再计算一次。
  • 空间复杂度：$O(1)$

    刷题心得

很多同学都被递归绕进去了，其实把递归函数当做普通函数就好了。

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！