সোয়্যাপ দিয়ে সবচেয়ে দীর্ঘ রিপিটেড ক্যারেক্টার সাবস্ট্রিং (C++)

এই সমস্যায় একটি স্ট্রিং দেওয়া আছে। স্ট্রিং-এর দুটি ক্যারেক্টার সোয়্যাপ করার অনুমতি আছে। সোয়্যাপ করার পর সবচেয়ে দীর্ঘ রিপিটেড ক্যারেক্টার সাবস্ট্রিং-এর দৈর্ঘ্য বের করতে হবে।

উদাহরণ

ইনপুট: "ababa"

আউটপুট: 3

ব্যাখ্যা: প্রথম 'b' এবং শেষ 'a' সোয়্যাপ করলে "aaabb" হয়, সবচেয়ে দীর্ঘ রিপিটেড সাবস্ট্রিং "aaa" (দৈর্ঘ্য ৩)।

অ্যালগরিদম (স্লাইডিং উইন্ডো + ফ্রিকোয়েন্সি ম্যাপ)

একটি ফ্রিকোয়েন্সি ম্যাপ m দিয়ে প্রতিটি ক্যারেক্টারের মোট কাউন্ট রাখুন।
স্লাইডিং উইন্ডো [j, i] মেইন্টেইন করুন যেখানে Höchst ২টি ভিন্ন ক্যারেক্টার থাকে এবং তাদের মধ্যে সবচেয়ে বেশি ফ্রিকোয়েন্সি যেটা, সেটি বাইরে আরও আছে কিনা চেক করুন।
উইন্ডো আপডেট করলে সর্বোচ্চ দৈর্ঘ্য ট্র্যাক করুন।

C++ প্রোগ্রাম

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

class Solution {
public:
    int maxRepOpt1(string text) {
        int ret = 1;
        map<char, int> cnt;
        int j = 0, n = text.size();
        set<char> x;
        map<char, int> m;
        for (char c : text) m[c]++;

        char a = '*', b = '*';
        for (int i = 0; i < n; i++) {
            cnt[text[i]]++;
            x.insert(text[i]);

            if (cnt[text[i]] == 2) {
                if (a == '*') a = text[i];
                else b = text[i];
            }

            while (a != '*' && b != '*' || x.size() > 2) {
                cnt[text[j]]--;
                if (cnt[text[j]] == 1) {
                    if (text[j] == a) a = '*';
                    else b = '*';
                }
                if (cnt[text[j]] == 0) x.erase(text[j]);
                j++;
            }

            char greater = (cnt[a] > cnt[b]) ? a : b;
            if (x.size() == 1 || m[greater] - cnt[greater] > 0)
                ret = max(ret, i - j + 1);
            else
                ret = max(ret, i - j);
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.maxRepOpt1("ababa");
    return 0;
}