C++-এ একটি স্ট্রিংয়ের সব সাবস্ট্রিং-এর יূনিক ক্যারেক্টার গণনা

ধরুন আমরা একটি ফাংশন countUniqueChars(s) ডিফাইন করি যা স্ট্রিং s-এ কতগুলো यূনিক (একবার আবির্ভূত) ক্যারেক্টার আছে তা রিটার্ন করে। উদাহরণস্বরূপ, s = "HELLOWORLD" হলে "H", "E", "W", "R", "D" - এই ৫টি ক্যারেক্টার একবারই আসছে, তাই countUniqueChars(s) = 5।

এখন এই সমস্যায় একটি স্ট্রিং s দেওয়া থাকলে, s-এর সকল সাবস্ট্রিং t এর জন্য countUniqueChars(t) এর যোগফল বের করতে হবে। (সাবস্ট্রিং রিপিট হলেও প্রতিবার আলাদা করে গণনা করতে হবে।)

উত্তর বড় হতে পারে, তাই মডুলো 10^9+7 ব্যবহার করুন।

উদাহরণ

ইনপুট: "HELLOWORLD" → আউটপুট: 128

সমাধানের ধাপসমূহ

add() এবং mul() ফাংশন তৈরি করুন মডুলো অপারেশনের জন্য।
প্রতিটি ক্যারেক্টারের ('A' থেকে 'Z') অবস্থান সমূহ সংগ্রহ করুন।
প্রতিটি ক্যারেক্টারের জন্য, তার যেকোনো দুটি последовательной অবস্থানের মধ্যবর্তী দূরত্বের গুণফল যোগ করুন।
সর্বমোট যোগফল রিটার্ন করুন।

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;

class Solution {
public:
    lli add(lli a, lli b) {
        return (a % m + b % m) % m;
    }
    
    lli mul(lli a, lli b) {
        return (a % m * b % m) % m;
    }
    
    int uniqueLetterString(string s) {
        int n = s.size();
        int ans = 0;
        vector<int> cnt[26];
        
        for (int i = 0; i < n; i++) {
            char x = s[i];
            if (cnt[x - 'A'].size() == 0) {
                cnt[x - 'A'].push_back(-1);
            }
            cnt[x - 'A'].push_back(i);
        }
        
        for (int i = 0; i < 26; i++) {
            if (cnt[i].size() == 0) continue;
            cnt[i].push_back(n);
            for (int j = 1; j < cnt[i].size() - 1; j++) {
                lli temp = mul(cnt[i][j] - cnt[i][j - 1], cnt[i][j + 1] - cnt[i][j]);
                ans = add(ans, temp);
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << (ob.uniqueLetterString("HELLOWORLD"));
}

ইনপুট

"HELLOWORLD"