C++ এ প্রদত্ত স্ট্রিং-এর সমস্ত সাবস্ট্রিং-এর অনন্য অক্ষর গণনা করুন

ধরুন আমরা countUniqueChars(s) নামক একটি ফাংশন সংজ্ঞায়িত করতে চাই যা s-এ অনন্য অক্ষরের সংখ্যা প্রদান করবে, তাই যদি s ="HELLOWORLD" তাহলে "H", "E", "W", "R", "D" হল অনন্য অক্ষর যেহেতু সেগুলি s-তে একবারই দেখা যায়, তাই কাউন্ট ইউনিকচার্স(গুলি) =5৷

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

যেহেতু উত্তরটি অনেক বড় হতে পারে, আমরা উত্তর মডিউল 10^9+7 ফেরত দিতে পারি।

সুতরাং, ইনপুট যদি "HELLOWORLD" এর মত হয়, তাহলে আউটপুট হবে 128

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন add() সংজ্ঞায়িত করুন, এটি a, b,
লাগবে
রিটার্ন (a mod m) + (b mod m)
একটি ফাংশন mul() সংজ্ঞায়িত করুন, এটি a, b,
লাগবে
রিটার্ন (a mod m) * (b mod m)
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
n :=s
এর আকার
উত্তর :=0
26 আকারের একটি অ্যারে cnt সংজ্ঞায়িত করুন
আরম্ভ করার জন্য i :=0, যখন i
- x :=s[i]
- যদি cnt[x - 'A'] এর আকার 0 এর সমান হয়, তাহলে −
  - cnt[x - 'A']
    এর শেষে -1 সন্নিবেশ করুন
- cnt[x - 'A']
  এর শেষে i ঢোকান
আরম্ভ করার জন্য i :=0, যখন i <26, আপডেট (i 1 দ্বারা বৃদ্ধি), −
- যদি cnt[i] এর আকার 0 এর সমান হয়, তাহলে −
  - নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
- cnt[i]
  এর শেষে n সন্নিবেশ করান
- j শুরু করার জন্য :=1, যখন j
  - temp :=mul(cnt[i, j] - cnt[i, j - 1], cnt[i, j + 1] - cnt[i, j])
  - ans :=add(ans, temp)
উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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);
   }
   lli mul(lli a, lli b){
      return (a % m) * (b % 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;
   }
};
main(){
   Solution ob;
   cout << (ob.uniqueLetterString("HELLOWORLD"));
}

ইনপুট

"HELLOWORLD"