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

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

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

思路分析

分治法

参考代码

func longestSubstring(s string, k int) int {
	if len(s) == 0 || k > len(s) {
		return 0
	}

	charCount := make(map[byte]int)
	for i := 0; i < len(s); i++ {
		charCount[s[i]]++
	}

	for char, count := range charCount {
		if count < k {
			maxLen := 0
			substrs := strings.Split(s, string(char))
			for _, substr := range substrs {
				maxLen = max(maxLen, longestSubstring(substr, k))
			}
			return maxLen
		}
	}

	return len(s)
}

时间复杂度：O (n * m)，其中 n 是字符串的长度，m 是不同字符的数量。

空间复杂度：O (n)，用于存储字符出现次数的哈希表和递归调用栈。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/04570603