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

समस्या विवरण

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

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

उत्तर बहुत बड़ा हो सकता है, इसलिए मॉड्यूलो 10^9 + 7 लौटाएं।

उदाहरण

इनपुट

"HELLOWORLD"

आउटपुट

समाधान दृष्टिकोण

प्रत्येक अक्षर के योगदान की गणना करें। प्रत्येक अक्षर के लिए, उसके घटनाओं (occurrences) के सूचकांक (indices) संग्रहीत करें। फिर प्रत्येक घटना के लिए, उसके बाएं और दाएं पड़ोसी घटनाओं के बीच की दूरी के गुणनफल से उसका योगदान निकालें।

प्रत्येक अक्षर के लिए सूचकांकों की सूची बनाएं, -1 और n से पैड करें।
प्रत्येक घटना के लिए: योगदान = (i - prev) × (next - i)
सभी योगदानों का योग लें।

कार्यकारी प्रोग्राम

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

class Solution {
public:
    lli add(lli a, lli b) {
        return (a % MOD + b % MOD) % MOD;
    }
    lli mul(lli a, lli b) {
        return (a % MOD * b % MOD) % MOD;
    }
    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");
    return 0;
}