C++-এ Longest Substring with At Least K Repeating Characters

এই সমস্যায় একটি স্ট্রিং s এবং ইন্টিজার k দেওয়া থাকলে, এমন সবচেয়ে লম্বা সাবস্ট্রিং T বের করতে হবে যাতে T-এ প্রতিটি ক্যারেক্টার কমপক্ষে k বার থাকে।

উদাহরণ: s="ababbc", k=2 -> আউটপুট 5 (সাবস্ট্রিং "ababb", যেখানে a ২ বার, b ৩ বার)।

সমাধানের পদ্ধতি (Divide & Conquer / Recursive)

বেস কেস: k <= 1 হলে পুরো স্ট্রিং রিটার্ন; s.size() < k হলে ০।
স্ট্রিং-এ সব ক্যারেক্টার কাউন্ট করুন।
যে ক্যারেক্টারের ফ্রিকোয়েন্সি k-এর চেয়ে কম, সেটি "ব্যাড ক্যারেক্টার"। সেটি দিয়ে স্ট্রিং স্প্লিট করুন।
প্রতিটি স্প্লিট পার্টে রিকার্শিভলি কল করুন এবং ম্যাক্সিমাম নিন।
যদি কোনো ব্যাড ক্যারেক্টার নেই, পুরো স্ট্রিংটি বৈধ।

উদাহরণ (C++)

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

class Solution {
public:
    vector<string> splitString(const string& s, char delim) {
        vector<string> res;
        string cur;
        for (char c : s) {
            if (c == delim) {
                if (!cur.empty()) { res.push_back(cur); cur.clear(); }
            } else cur += c;
        }
        if (!cur.empty()) res.push_back(cur);
        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 = 0;
        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) << endl;
    return 0;
}

ইনপুট

"ababbc" 2

আউটপুট

কমপ্লেক্সিটি: O(n) গড়ে, কারণ প্রতিটি রিকার্শন লেভেলে স্ট্রিং ছোট হয় এবং প্রতিটি ক্যারেক্টার কনস্ট্যান্ট বার প্রসেস হয়।