class Solution {
public:
    int longestSubstring(string s, int k) {
        if (s.size() < k)
            return 0;
        
        // 统计频数
        vector<int> cnt(26, 0);
        for (auto ch : s)
            cnt[ch - 'a']++;

        // 记录分割位点
        vector<int> split;
        for (int i = 0; i < s.size(); i++)
        {
            if (cnt[s[i] - 'a'] < k)
            {
                split.push_back(i);
            }
        }
        
        if (split.size() == 0)  // 无需分割
            return s.size();

        int start = 0;  // 当前子串的起点
        int res = 0;  // 最终答案
        for (auto pos : split)
        {
            // string.substr(pos, len)
            // 从位置pos开始的连续len个字符
            res = max(res, longestSubstring(s.substr(start, pos - start), k));
            start = pos + 1;
        }
        if (start != s.size() - 1)  // 对于最后一个子串
        {
            res = max(res, longestSubstring(s.substr(start, s.size() - start), k));
        }
        return res;
    }
};