सी ++ में दिए गए स्ट्रिंग के सभी सबस्ट्रिंग के अद्वितीय वर्णों की गणना करें

मान लीजिए कि हम countUniqueChars(s) नामक एक फ़ंक्शन को परिभाषित करना चाहते हैं जो s पर अद्वितीय वर्णों की संख्या लौटाएगा, इसलिए यदि s ="HELLOWORLD" तो "H", "E", "W", "R", "D" अद्वितीय वर्ण हैं क्योंकि वे s में केवल एक बार दिखाई देते हैं, इसलिए countUniqueChars(s) =5.

अब इस समस्या पर एक स्ट्रिंग दी गई है, हमें countUniqueChars(t) का योग ज्ञात करना है जहां t s का एक विकल्प है। (यहां कुछ सबस्ट्रिंग को दोहराया जा सकता है, इसलिए इस मामले में हमें दोहराए गए लोगों को भी गिनना होगा।)

चूंकि उत्तर बहुत बड़ा हो सकता है, हम उत्तर मॉड्यूल 10^9+7 वापस कर सकते हैं।

इसलिए, यदि इनपुट "HELLOWORLD" जैसा है, तो आउटपुट 128

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन ऐड () को परिभाषित करें, इसमें a, b,

  . लगेगा

• वापसी (एक मॉड एम) + (बी मॉड एम)

• फ़ंक्शन mul() को परिभाषित करें, इसमें a, b,

  . लगेगा

• वापसी (एक मॉड एम) * (बी मॉड एम)

• मुख्य विधि से, निम्न कार्य करें -

• n :=s का आकार

• उत्तर :=0

• 26 आकार की एक सरणी को परिभाषित करें

• इनिशियलाइज़ i:=0 के लिए, जब i

  • एक्स:=एस [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

    • अस्थायी:=mul(cnt[i, j] - cnt[i, j-1], cnt[i, j + 1] - cnt[i, j])

    • उत्तर:=जोड़ें (उत्तर, अस्थायी)

• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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