Longest Substring with At Least K Repeating Characters trong C++

Cho chuỗi s (chữ thường) và số k. Tìm độ dài substring dài nhất mà mọi ký tự trong nó xuất hiện ít nhất k lần.

Ví dụ: s="ababbc", k=2 → output 5, substring "ababb" (2 'a', 3 'b').

Giải thuật (Divide & Conquer / Đệ quy)

• Hàm longestSubstring(s, k):
  • Nếu k==1 trả về s.size().
  • Nếu s.size() < k trả về 0.
  • Đếm tần suất cnt[26].
  • Tìm badChar: ký tự có 0 < cnt < k.
  • Nếu không có badChar → trả về s.size().
  • Tách chuỗi s bằng badChar thành các đoạn.
  • Đệ quy tìm max trên các đoạn.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> splitString(string s, char x) {
        vector<string> res;
        string temp;
        for (char c : s) {
            if (c == x) {
                if (!temp.empty()) { res.push_back(temp); temp.clear(); }
            } else temp += c;
        }
        if (!temp.empty()) res.push_back(temp);
        return res;
    }
    int longestSubstring(string s, int k) {
        if (k == 1) return s.size();
        if (s.size() < k) return 0;
        vector<int> cnt(26, 0);
        for (char c : s) cnt[c-'a']++;
        char badChar = '*';
        for (int i = 0; i < 26; i++)
            if (cnt[i] > 0 && cnt[i] < k) { badChar = 'a' + i; break; }
        if (badChar == '*') return s.size();
        vector<string> parts = splitString(s, badChar);
        int ans = 0;
        for (auto& part : parts) ans = max(ans, longestSubstring(part, k));
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.longestSubstring("ababbc", 2);
    return 0;
}

Input

"ababbc" 2

Output

5