কম্পিউটার

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"

আউটপুট

128

  1. একটি স্ট্রিংয়ের সমস্ত স্বতন্ত্র অক্ষর C++ ক্রমে প্রিন্ট করুন

  2. একটি প্রদত্ত স্ট্রিং এর সমস্ত সাবস্ট্রিং C++ এ প্রিন্ট করার জন্য প্রোগ্রাম

  3. C++ এ স্ট্রিং এর সমস্ত অক্ষর টগল করুন

  4. C++ এ একটি প্রদত্ত স্ট্রিং-এ “1(0+)1”-এর সমস্ত প্যাটার্ন খুঁজুন