python - 不理解 "Longest Substring with At Least K Repeating Characters"的本质

Question

这是关于 LeetCode 问题 #395 的问题，标题为 "Longest Substring with At Least K Repeating Characters."

有人发布了一个非常简洁的解决方案(在 Python 中)，但我无法理解这种方法的核心思想。我可以机械地遵循代码(转载如下)，但我不能完全掌握这里的核心思想。例如，我看到它对字符串中的字符进行计数，并在计数小于规定的最大字符数 (k) 的字符处递归拆分字符串。

def longestSubstring(self, s, k):
    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)

作者说(强调)，“如果每个字符至少出现 k 次，则整个字符串都可以。否则按最不频繁的字符拆分(因为它总是太不频繁，因此不能成为任何 ok 子串的一部分) 并充分利用拆分。”

为什么当一个字符出现频率太低时，它必然不能成为任何有效子串的一部分？

Answer 1

来自问题:

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

问题指出字符串中的每个字符需要至少出现 k 次，因此每个出现频率太低的字符都不能成为任何子字符串的一部分。