class Solution {
public:
int longestSubstring(string s, int k) {
}
};
395. 至少有 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 次。
提示：
1 <= s.length <= 104s 仅由小写英文字母组成1 <= k <= 105原站题解
java 解法, 执行用时: 4 ms, 内存消耗: 41.3 MB, 提交时间: 2022-12-14 12:45:37
class Solution {
public int longestSubstring(String s, int k) {
if (s.length() < k) return 0;
HashMap<Character, Integer> counter = new HashMap();
for (int i = 0; i < s.length(); i++) {
counter.put(s.charAt(i), counter.getOrDefault(s.charAt(i), 0) + 1);
}
for (char c : counter.keySet()) {
if (counter.get(c) < k) {
int res = 0;
for (String t : s.split(String.valueOf(c))) {
res = Math.max(res, longestSubstring(t, k));
}
return res;
}
}
return s.length();
}
}
python3 解法, 执行用时: 32 ms, 内存消耗: 15 MB, 提交时间: 2022-12-14 12:45:05
class Solution(object):
def longestSubstring(self, s, k):
if len(s) < k:
return 0
for c in set(s):
if s.count(c) < k:
return max(self.longestSubstring(t, k) for t in s.split(c))
return len(s)
java 解法, 执行用时: 8 ms, 内存消耗: 39.8 MB, 提交时间: 2022-12-14 12:44:43
class Solution {
public int longestSubstring(String s, int k) {
int ret = 0;
int n = s.length();
for (int t = 1; t <= 26; t++) {
int l = 0, r = 0;
int[] cnt = new int[26];
int tot = 0;
int less = 0;
while (r < n) {
cnt[s.charAt(r) - 'a']++;
if (cnt[s.charAt(r) - 'a'] == 1) {
tot++;
less++;
}
if (cnt[s.charAt(r) - 'a'] == k) {
less--;
}
while (tot > t) {
cnt[s.charAt(l) - 'a']--;
if (cnt[s.charAt(l) - 'a'] == k - 1) {
less++;
}
if (cnt[s.charAt(l) - 'a'] == 0) {
tot--;
less--;
}
l++;
}
if (less == 0) {
ret = Math.max(ret, r - l + 1);
}
r++;
}
}
return ret;
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-12-14 12:44:30
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
}
javascript 解法, 执行用时: 76 ms, 内存消耗: 43.3 MB, 提交时间: 2022-12-14 12:44:11
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var longestSubstring = function(s, k) {
let ret = 0;
const n = s.length;
for (let t = 1; t <= 26; t++) {
let l = 0, r = 0;
const cnt = new Array(26).fill(0);
let tot = 0;
let less = 0;
while (r < n) {
cnt[s[r].charCodeAt() - 'a'.charCodeAt()]++;
if (cnt[s[r].charCodeAt() - 'a'.charCodeAt()] === 1) {
tot++;
less++;
}
if (cnt[s[r].charCodeAt() - 'a'.charCodeAt()] === k) {
less--;
}
while (tot > t) {
cnt[s[l].charCodeAt() - 'a'.charCodeAt()]--;
if (cnt[s[l].charCodeAt() - 'a'.charCodeAt()] === k - 1) {
less++;
}
if (cnt[s[l].charCodeAt() - 'a'.charCodeAt()] === 0) {
tot--;
less--;
}
l++;
}
if (less == 0) {
ret = Math.max(ret, r - l + 1);
}
r++;
}
}
return ret;
};
javascript 解法, 执行用时: 64 ms, 内存消耗: 42.6 MB, 提交时间: 2022-12-14 12:43:51
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var longestSubstring = function(s, k) {
const n = s.length;
return dfs(s, 0, n - 1, k);
}
const dfs = (s, l, r, k) => {
const cnt = new Array(26).fill(0);
for (let i = l; i <= r; i++) {
cnt[s[i].charCodeAt() - 'a'.charCodeAt()]++;
}
let split = 0;
for (let i = 0; i < 26; i++) {
if (cnt[i] > 0 && cnt[i] < k) {
split = String.fromCharCode(i + 'a'.charCodeAt());
break;
}
}
if (split == 0) {
return r - l + 1;
}
let i = l;
let ret = 0;
while (i <= r) {
while (i <= r && s[i] === split) {
i++;
}
if (i > r) {
break;
}
let start = i;
while (i <= r && s[i] !== split) {
i++;
}
const length = dfs(s, start, i - 1, k);
ret = Math.max(ret, length);
}
return ret;
};
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2022-12-14 12:43:32
func longestSubstring(s string, k int) (ans int) {
if s == "" {
return
}
cnt := [26]int{}
for _, ch := range s {
cnt[ch-'a']++
}
var split byte
for i, c := range cnt[:] {
if 0 < c && c < k {
split = 'a' + byte(i)
break
}
}
if split == 0 {
return len(s)
}
for _, subStr := range strings.Split(s, string(split)) {
ans = max(ans, longestSubstring(subStr, k))
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
java 解法, 执行用时: 0 ms, 内存消耗: 39.5 MB, 提交时间: 2022-12-14 12:43:16
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;
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.5 MB, 提交时间: 2022-12-14 12:43:01
// 分治
class Solution {
public:
int dfs(const string& s, int l, int r, int k) {
vector<int> cnt(26, 0);
for (int i = l; i <= r; i++) {
cnt[s[i] - 'a']++;
}
char split = 0;
for (int i = 0; i < 26; i++) {
if (cnt[i] > 0 && cnt[i] < k) {
split = i + 'a';
break;
}
}
if (split == 0) {
return r - l + 1;
}
int i = l;
int ret = 0;
while (i <= r) {
while (i <= r && s[i] == split) {
i++;
}
if (i > r) {
break;
}
int start = i;
while (i <= r && s[i] != split) {
i++;
}
int length = dfs(s, start, i - 1, k);
ret = max(ret, length);
}
return ret;
}
int longestSubstring(string s, int k) {
int n = s.length();
return dfs(s, 0, n - 1, k);
}
};