Longest Substring with At Least K Repeating Characters: สตริงย่อยที่มีตัวอักษรซ้ำ ≥ K ใน C++

ปัญหา

กำหนดสตริง s (Lowercase only) และ k หา ความยาวสตริงย่อย (Substring) ยาวที่สุด ที่ทุกตัวอักษรในสตริงย่อยนั้นปรากฏ ≥ k ครั้ง

ตัวอย่าง: s="ababbc", k=2 → "ababb" (a:2, b:3) → ความยาว 5

แนวคิด: Divide & Conquer (Recursive)

ข้อสังเกต

ถ้าตัวอักษร c ใน s ปรากฏ น้อยกว่า k ครั้ง → c ไม่สามารถอยู่ในคำตอบได้ → ใช้ c เป็น Delimiter แบ่งปัญหาเป็น Subproblems

Algorithm

1. นับ Frequency ทุกตัวอักษรใน s
2. หา badChar = ตัวอักษรแรกที่ freq < k
3. ถ้าไม่มี badChar → คืน s.length()
4. Split s ด้วย badChar ได้ Substrings หลายตัว
5. Recursive หาคำตอบในแต่ละ Substring → Max

โค้ด C++

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

class Solution {
    vector<string> splitString(const string& s, char delimiter) {
        vector<string> res;
        string curr;
        for (char c : s) {
            if (c == delimiter) {
                if (!curr.empty()) res.push_back(curr);
                curr.clear();
            } else {
                curr += c;
            }
        }
        if (!curr.empty()) res.push_back(curr);
        return res;
    }
    
public:
    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();  // ทุกตัว ≥ k
        
        vector<string> parts = splitString(s, badChar);
        int ans = 0;
        for (const string& part : parts) {
            ans = max(ans, longestSubstring(part, k));
        }
        return ans;
    }
};

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

การทำงานตัวอย่าง

s="ababbc", k=2
freq: a=2, b=3, c=1  → badChar='c'
split by 'c': ["ababb"]
  s="ababb", k=2
  freq: a=2, b=3  → no badChar → return 5
Answer: 5

ความซับซ้อน

• Time: O(n) Average, O(n²) Worst case (ทุกครั้ง Split แค่ 1 ตัว)
• Space: O(n) Recursion stack + Substrings

Input / Output

Input:  "ababbc" 2
Output: 5