395. Longest Substring with At Least K Repeating Characters #

题目 #

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

Example 1:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input: s = "ababbc", k = 2
Output: 5
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Constraints:

1 <= s.length <= 10^4
s consists of only lowercase English letters.
1 <= k <= 10^5

题目大意 #

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串，要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

解题思路 #

最容易想到的思路是递归。如果某个字符出现次数大于 0 小于 k，那么包含这个字符的子串都不满足要求。所以按照这个字符来切分整个字符串，满足题意的最长子串一定不包含切分的字符。切分完取出最长子串即可。时间复杂度 O(26*n)，空间复杂度 O(26^2)
此题另外一个思路是滑动窗口。有一个需要解决的问题是右窗口移动的条件。此题要求最长字符串，那么这个最终的字符串内包含的字符种类最多是 26 种。字符种类就是右窗口移动的条件。依次枚举字符种类，如果当前窗口内的字符种类小于当前枚举的字符种类，那么窗口右移，否则左移。窗口移动中需要动态维护 freq 频次数组。可以每次都循环一遍这个数组，计算出出现次数大于 k 的字符。虽然这种做法只最多循环 26 次，但是还是不高效。更高效的做法是维护 1 个值，一个用来记录当前出现次数小于 k 次的字符种类数 less。如果 freq 为 0 ，说明小于 k 次的字符种类数要发生变化，如果是右窗口移动，那么 less++，如果是左窗口移动，那么less--。同理，如果 freq 为 k ，说明小于 k 次的字符种类数要发生变化，如果是右窗口移动，那么 less--，如果是左窗口移动，那么less++。在枚举 26 个字符种类中，动态维护记录出最长字符串。枚举完成，最长字符串长度也就求出来了。时间复杂度 O(26*n)，空间复杂度 O(26)

代码 #

package leetcode

import "strings"

// 解法一 滑动窗口
func longestSubstring(s string, k int) int {
	res := 0
	for t := 1; t <= 26; t++ {
		freq, total, lessK, left, right := [26]int{}, 0, 0, 0, -1
		for left < len(s) {
			if right+1 < len(s) && total <= t {
				if freq[s[right+1]-'a'] == 0 {
					total++
					lessK++
				}
				freq[s[right+1]-'a']++
				if freq[s[right+1]-'a'] == k {
					lessK--
				}
				right++
			} else {
				if freq[s[left]-'a'] == k {
					lessK++
				}
				freq[s[left]-'a']--
				if freq[s[left]-'a'] == 0 {
					total--
					lessK--
				}
				left++
			}
			if lessK == 0 {
				res = max(res, right-left+1)
			}

		}
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 解法二 递归分治
func longestSubstring1(s string, k int) int {
	if s == "" {
		return 0
	}
	freq, split, res := [26]int{}, byte(0), 0
	for _, ch := range s {
		freq[ch-'a']++
	}
	for i, c := range freq[:] {
		if 0 < c && c < k {
			split = 'a' + byte(i)
			break
		}
	}
	if split == 0 {
		return len(s)
	}
	for _, subStr := range strings.Split(s, string(split)) {
		res = max(res, longestSubstring1(subStr, k))
	}
	return res
}

⬅️上一页

下一页➡️