至少有K个重复字符的最长子串

发表于
本文字数： 321 阅读时长 ≈ 1 分钟

LeetCode每日一题，395. Longest Substring with At Least K Repeating Characters

先看题目描述

6SIrTS.png

大意就是给定一个只包含小写字母的字符串 s 和一个整数 k，让我们找出 s 的最长子串，满足其中每种字母的出现次数都不小于 k

算法和思路

这题想了好久没想出来，就去看题接了，才理解

分治

对于字符串 s，如果存在某个字符 ch，它的出现次数大于 0 且小于 k，则任何包含 ch 的子串都不可能满足要求。也就是说，我们将字符串按照 ch 切分成若干段，则满足要求的最长子串一定出现在某个被切分的段内，而不能跨越一个或多个段。因此，可以考虑分治的方式求解本题

算法源码

分治

1
2