সর্বোच्च Анаগ্রাম সাবস্ট্রিং গণনা (C++ প্রোগ্রাম)

আমাদের ইনপুট হিসেবে একটি স্ট্রিং str[] দেওয়া আছে। লক্ষ্য হল str[]-এ কতগুলো অনাগ্রাম (anagram) সাবস্ট্রিং আছে সেটি গণনা করা। دو স্ট্রিং একে অপরের অনাগ্রাম হয় যদি সেগুলোতে একই সংখ্যক অক্ষর থাকে এবং সকল অক্ষর দুটোতেই থাকে। অক্ষরের ক্রম ভিন্ন হতে পারে।

"abc" হল "cba", "bca" ইত্যাদির অনাগ্রাম।

ইনপুট: str[] = "abccb"

আউটপুট: সর্বোচ্চ অনাগ্রাম সাবস্ট্রিং গণনা: 4

ব্যাখ্যা: অনাগ্রামগুলো: (b,b), (c,c), (bc,cb), (bcc,ccb)

ইনপুট: str = "aaa"

আউটপুট: সর্বোচ্চ অনাগ্রাম সাবস্ট্রিং গণনা: 4

ব্যাখ্যা: অনাগ্রামগুলো: (a,a), (a,a), (a,a), (aa,aa)

আমরা একটি ম্যাপ নিচ্ছি যেটিতে ভেক্টর থাকবে ইংরেজি বর্ণমালার ফ্রিকোয়েন্সি (frequency) সাবস্ট্রিং-এ এবং সেই ফ্রিকোয়েন্সি সমন্বিত সাবস্ট্রিংয়ের গণনা। map, int> mp_vec; vector vec(MAX, 0) যেটি সাবস্ট্রিং-এ সকল ২৬ অক্ষরের ফ্রিকোয়েন্সি সংরক্ষণ করবে। এবং ম্যাপ করা ইন্টিজার হবে সেই ফ্রিকোয়েন্সি ভেক্টর সমন্বিত সাবস্ট্রিংয়ের গণনা। প্রতিটি সাবস্ট্রিংয়ের জন্য যদি গণনা x হয় অনাগ্রামের জন্য। তবে মোট অনাগ্রাম জোড়া হবে x*(x-1)/2।

• স্ট্রিং str[] ক্যারেক্টার অ্যারে হিসেবে নিন।
• anagram_substring(string str, int length) ফাংশন স্ট্রিং নেয় এবং সর্বোচ্চ অনাগ্রাম সাবস্ট্রিং গণনা ফেরত দেয়।
• আরম্ভিক গণনা ০ নিন।
• একটি ম্যাপ নিন, map, int> mp_vec;।
• দুটি for লুপ দিয়ে str[] ট্রভার্স করুন i=0 থেকে i
• প্রতিটি সাবস্ট্রিং str[i to j]-এর জন্য। vector vec(MAX, 0); যেটি সাবস্ট্রিং-এ ইংরেজি অক্ষরগুলোর গণনা ধারণ করবে।
• বর্তমান ক্যারেক্টার c হিসেবে str[j] নিন। এর পূর্ণসংখ্যা মান temp=c-'a' দিয়ে নিন।
• ফ্রিকোয়েন্সি আপডেট করুন vec[temp]++।
• এই ফ্রিকোয়েন্সি ভেক্টরের সাথে মিলে যাওয়া সাবস্ট্রিংয়ের গণনা বাড়ান mp_vec[vec]++।
• এখন সব ফ্রিকোয়েন্সি ভেক্টর ধারণকারী ম্যাপ ট্রভার্স করুন for লুপ দিয়ে iterator it=mp_vec.begin() থেকে it != mp_vec.end() পর্যন্ত।
• প্রতিটি গণনা it->second হিসেবে, ((last) * (last-1))/2 কে count-এ যোগ করুন সকল অনাগ্রাম জোড়ার জন্য।
• শেষে সব অনাগ্রামের গণনা পাওয়া যাবে।
• ফলাফল হিসেবে count ফেরত দিন।

#include 
using namespace std;

#define MAX 26

int anagram_substring(string str, int length) {
    int count = 0;
    map, int> mp_vec;
    for (int i = 0; i < length; i++) {
        vector vec(MAX, 0);
        for (int j = i; j < length; j++) {
            char c = str[j];
            char temp = c - 'a';
            vec[temp]++;
            mp_vec[vec]++;
        }
    }
    for (auto it = mp_vec.begin(); it != mp_vec.end(); it++) {
        int last = it->second;
        count += ((last) * (last - 1)) / 2;
    }
    return count;
}

int main() {
    string str = "TP";
    int length = str.length();
    cout << "Count of total anagram substrings are: " << anagram_substring(str, length) << endl;
    return 0;
}

Count of total anagram substrings are: 3