C++-এ একই শুরু ও শেষ ক্যারেক্টার বিশিষ্ট সাবস্ট্রিং গণনা

আমাদের একটি স্ট্রিং str দেওয়া আছে। লক্ষ্য হলো str-এ কতগুলো সাবস্ট্রিং আছে যাদের শুরু এবং শেষ ক্যারেক্টার একই। উদাহরণস্বরূপ, ইনপুট "baca" হলে সাবস্ট্রিং: "b", "a", "c", "a", "aca"। মোট ৫টি।

উদাহরণ দিয়ে বুঝি

ইনপুট − str="abaefgf"

আউটপুট − একই শুরু ও শেষ ক্যারেক্টার বিশিষ্ট সাবস্ট্রিং: ৯

ব্যাখ্যা − সাবস্ট্রিং: "a", "b", "a", "e", "f", "g", "f", "aba", "fgf"। মোট ৯।

ইনপুট − str="abcdef"

আউটপুট − একই শুরু ও শেষ ক্যারেক্টার বিশিষ্ট সাবস্ট্রিং: ৬

ব্যাখ্যা − সাবস্ট্রিং: "a", "b", "c", "d", "e", "f"। মোট ৬।

প্রোগ্রামে ব্যবহৃত পদ্ধতি

এই সমস্যা সমাধানের একাধিক পদ্ধতি আছে: নেভ הפשט এবং দক্ষ পদ্ধতি। প্রথমে নেভ הפשט পদ্ধতি দেখি। প্রতিটি দৈর্ঘ্যের সাবস্ট্রিং check() ফাংশনে পাস করব। যদি সাবস্ট্রিং-এর প্রথম এবং শেষ ক্যারেক্টার একই হয়, কাউন্ট বাড়াব।

• স্ট্রিং str। দৈর্ঘ্য str.size()।
• check(string str) ফাংশন সাবস্ট্রিং নিয়ে প্রথম ও শেষ ক্যারেক্টার একই কিনা চেক করে (str[0]==str[length-1])। সত্য হলে ১ রিটার্ন।
• check_Start_End(string str, int length) ফাংশন স্ট্রিং এবং দৈর্ঘ্য নিয়ে একই শুরু-শেষ ক্যারেক্টার সাবস্ট্রিং কাউন্ট রিটার্ন করে।
• প্রাথমিক কাউন্ট ০।
• দুটি for লুপ: i=0 থেকে length, ইনার j=1 থেকে length-1।
• substr(i,j) দিয়ে সব দৈর্ঘ্যের সাবস্ট্রিং পান। check()-এ পাস করুন। ১ রিটার্ন করলে কাউন্ট বাড়ান।
• দুই লুপ শেষে count রিটার্ন করুন।

দক্ষ পদ্ধতি (Efficient Approach)

উত্তর প্রতিটি ক্যারেক্টারের ফ্রিকোয়েন্সির ওপর নির্ভর করে। উদাহরণস্বরূপ, "bacba"-এ 'b'-র ফ্রিকোয়েন্সি ২ এবং 'b'-সহ সাবস্ট্রিং: "b", "bacb", "b"। যেটা 2+1C2 = 3। আমরা প্রতিটি ক্যারেক্টারের ফ্রিকোয়েন্সি বের করে freq*(freq+1)/2 যোগ করব।

• স্ট্রিং str। দৈর্ঘ্য str.size()।
• check_Start_End(string str, int length) ফাংশন স্ট্রিং এবং দৈর্ঘ্য নিয়ে একই শুরু-শেষ ক্যারেক্টার সাবস্ট্রিং কাউন্ট রিটার্ন করে।
• প্রাথমিক কাউন্ট ০।
• arr[26] অ্যারে ফ্রিকোয়েন্সি স্টোর করতে।
• স্ট্রিং ট্রাভার্স করে arr[str[i]-'a']++।
• arr[26] ট্রাভার্স করে প্রতিটি ফ্রিকোয়েন্সি arr[i]*(arr[i]+1)/2 কাউন্টে যোগ করুন।
• count রিটার্ন করুন।

উদাহরণ (নেভ הפשט পদ্ধতি)

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

int check(string str) {
    int length = str.length();
    if (str[0] == str[length-1]) {
        return 1;
    }
    return 0;
}

int check_Start_End(string str, int length) {
    int count = 0;
    for (int i = 0; i < length; i++) {
        for (int j = 1; j <= length-i; j++) {
            if (check(str.substr(i, j))) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    string str = "bcbdedfef";
    int length = str.length();
    cout << "Count of substrings with same first and last characters are: " << check_Start_End(str, length);
    return 0;
}

আউটপুট

Count of substrings with same first and last characters are: 13

উদাহরণ (দক্ষ পদ্ধতি)

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

int check_Start_End(string str, int length) {
    int count = 0;
    int arr[maximum] = {0};
    for (int i = 0; i < length; i++) {
        arr[str[i] - 'a']++;
    }
    for (int i = 0; i < maximum; i++) {
        count = count + (arr[i] * (arr[i] + 1) / 2);
    }
    return count;
}

int main() {
    string str = "bcbdedfef";
    int length = str.length();
    cout << "Count of substrings with same first and last characters are: " << check_Start_End(str, length);
    return 0;
}

আউটপুট

Count of substrings with same first and last characters are: 13