Go Java算法之K个重复字符最长子串详解
目录
- 至少有K个重复字符的最长子串
- 方法一:分治(Java)
- 方法二:滑动窗口(go)
至少有K个重复字符的最长子串
给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串, 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
- 示例 1:
输入:s = "aaabb", k = 3
输出:3
解释:最长子串为 "aaa" ,其中 'a' 重复了 3 次。
- 示例 2:
输入:s = "ababbc", k = 2
输出:5
解释:最长子串为 "ababb" ,其中 'a' 重复了 2 次, 'b' 重复了 3 次。
方法一:分治(Java)
对于字符串 s,如果存在某个字符 ch,它的出现次数大于 0 且小于 k,则任何包含 ch 的子串都不可能满足要求。
也就是说,我们将字符串按照 ch 切分成若干段,则满足要求的最长子串一定出现在某个被切分的段内,而不能跨越一个或多个段。
具体思路:
- 先整体考虑,如果某个字符在整个字符串中的出现次数 < k,那它一定不会出现在合法子串中。
- s: aaabbaa,k: 3,b 只出现 2 次,它肯定不会出现在合法子串中,要到它的两侧找。
- 考察aaa和aa,变成一个规模较小的子问题,递归去求aaa和aa中合法子串的最长长度。
- 当递归到子问题的规模足够小,即,子串的长度小于 k,即便子串的字符都相同,字符的出现次数也小于 k,所以没有合法子串,返回 0
class Solution { public int longestSubstring(String s, int k) { int n = s.length(); return dfs(s, 0, n - 1, k); } public int dfs(String s, int l, int r, int k) { int[] cnt = new int[26]; for (int i = l; i <= r; i++) { cnt[s.charAt(i) - 'a']++; } char split = 0; for (int i = 0; i < 26; i++) { if (cnt[i] > 0 && cnt[i] < k) { split = (char) (i + 'a'); break; } } if (split == 0) { return r - l + 1; } int i = l; int ret = 0; while (i <= r) { while (i <= r && s.charAt(i) == split) { i++; } if (i > r) { break; } int start = i; while (i <= r && s.charAt(i) != split) { i++; } int length = dfs(s, start, i - 1, k); ret = Math.max(ret, length); } return ret; } }
N:为字符串的长度
Σ 为字符集
时间复杂度:O(N⋅∣Σ∣)
空间复杂度:O(∣Σ∣^2)
方法二:滑动窗口(go)
对于给定的字符种类数量 t,我们维护滑动窗口的左右边界 l,r 滑动窗口内部每个字符出现的次数 cnt,以及滑动窗口内的字符种类数目 total。
当 total>t 时,我们不断地右移左边界 l,并对应地更新 cnt 以及 total,直到 total≤t 为止。这样,对于任何一个右边界 r,我们都能找到最小的 l(记为 l_{min}),使得 s[l_{min}...r]之间的字符种类数目不多于 t。
通过维护额外的计数器 less,我们无需遍历 cnt 数组,就能知道每个字符是否都出现了至少 k 次,同时可以在每次循环时,在常数时间内更新计数器的取值。
func longestSubstring(s string, k int) (ans int) { for t := 1; t <= 26; t++ { cnt := [26]int{} total := 0 lessK := 0 l := 0 for r, ch := range s { ch -= 'a' if cnt[ch] == 0 { total++ lessK++ } cnt[ch]++ if cnt[ch] == k { lessK-- } for total > t { ch := s[l] - 'a' if cnt[ch] == k { lessK++ } cnt[ch]-- if cnt[ch] == 0 { total-- lessK-- } l++ } if lessK == 0 { ans = max(ans, r-l+1) } } } return ans } func max(a, b int) int { if a > b { return a } return b }
N:为字符串的长度
Σ 为字符集
时间复杂度:O(N⋅∣Σ∣+∣Σ∣^2)
空间复杂度:O(∣Σ∣)
以上就是Go Java算法之K个重复字符最长子串详解的详细内容,更多关于Go Java算法重复字符子串的资料请关注我们其它相关文章!