C++-এ নির্দিষ্ট ক্যারেক্টার অন্তত একবার থাকা সাবস্ট্রিং সংখ্যা গণনা

আমাদের একটি স্ট্রিং str[] এবং একটি ক্যারেক্টার X দেওয়া আছে। লক্ষ্য হল স্ট্রিং-র যেসব সাবস্ট্রিং-এ X অন্তত একবার আছে সেগুলোর সংখ্যা বের করা।

উদাহরণ

ইনপুট: str[] = "aabccd", X = 'c'

আউটপুট: ১৪

ব্যাখ্যা: সাবস্ট্রিংগুলো: "c", "c", "bc", "cc", "cd", "abc", "bcc", "ccd", "aabc", "abcc", "bccd", "aabcc", "abccd", "aabccd"।

ইনপুট: str[] = "settings", X = 's'

আউটপুট: ১৪

অ্যালগরিদম

মোট সাবস্ট্রিং সংখ্যা = n*(n+1)/2। আমরা X না থাকা সাবস্ট্রিং বাদ দিয়ে কাজ করি। স্ট্রিং ট্রাভার্স করে X পাওয়া পর্যন্ত ক্যারেক্টার কাউন্ট temp রাখুন। X পেলে, নতুন সাবস্ট্রিং সংখ্যা = (temp+1) * (length-i)। এটা কাউন্টে যোগ করুন এবং temp=0 রিসেট করুন।

1. স্ট্রিং, দৈর্ঘ্য এবং ক্যারেক্টার x ইনপুট নিন।
2. count = 0, temp = 0।
3. স্ট্রিং ট্রাভার্স করুন: যদি str[i] != x হয় তবে temp++।
4. যদি str[i] == x হয়: count += (temp+1) * (length-i); temp = 0।
5. শেষে count ফেরত দিন।

C++ বাস্তবায়ন

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

int sub_x(string str, int length, char x) {
    int count = 0;
    int temp = 0;
    for (int i = 0; i < length; i++) {
        if (str[i] == x) {
            int temp_2 = temp + 1;
            count += temp_2 * (length - i);
            temp = 0;
        } else {
            temp++;
        }
    }
    return count;
}

int main() {
    string str = "abcabbc";
    int length = str.length();
    char x = 'a';
    cout << "Count of sub-strings that contain character X at least once are: " 
         << sub_x(str, length, x);
    return 0;
}

আউটপুট

Count of sub-strings that contain character X at least once are: 19