C++ में कुल अनाग्राम उपस्ट्रिंग्स की गिनती

हमें इनपुट के रूप में एक स्ट्रिंग str[] दी गई है। लक्ष्य str[] में मौजूद अनाग्राम उपस्ट्रिंग्स की संख्या गिनना है। दो स्ट्रिंग्स एक-दूसरे की अनाग्राम हैं यदि उनमें समान संख्या में वर्ण हैं और सभी वर्ण दोनों में होते हैं। वर्णों का क्रम अलग हो सकता है।

"abc", "cba", "bca" आदि की अनाग्राम है।

आइए उदाहरणों से समझते हैं।

इनपुट - str[] = "abccb"

आउटपुट - कुल अनाग्राम उपस्ट्रिंग्स की गिनती - 4

व्याख्या - अनाग्राम हैं - (b,b), (c,c), (bc,cb), (bcc,ccb)

इनपुट - str = "aaa"

आउटपुट - कुल अनाग्राम उपस्ट्रिंग्स की गिनती - 4

व्याख्या - अनाग्राम हैं - (a,a), (a,a), (a,a), (aa,aa)

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण

हम एक मैप ले रहे हैं जिसमें अंग्रेजी वर्णमालाओं की आवृत्तियों वाले वेक्टर और सरणी में ऐसे उपस्ट्रिंग्स की गिनती होगी। map, int> mp_vec में; vector vec(MAX, 0) वर्तमान उपस्ट्रिंग में सभी 26 वर्णमालाओं की आवृत्ति संग्रहीत करेगा। और मैप किए गए पूर्णांक समान आवृत्ति वेक्टर वाले ऐसे उपस्ट्रिंग्स की गिनती होंगे। प्रत्येक उपस्ट्रिंग के लिए यदि अनाग्राम के लिए गिनती x है। तो कुल अनाग्राम युग्म x*(x-1)/2 होंगे।

• स्ट्रिंग str[] को वर्ण सरणी के रूप में लें।
• फ़ंक्शन anagram_substring(string str, int length) स्ट्रिंग लेता है और कुल अनाग्राम उपस्ट्रिंग्स की गिनती वापस करता है।
• प्रारंभिक गिनती 0 लें।
• एक मैप लें, map, int> mp_vec;
• दो फॉर लूप का उपयोग करके i=0 से i
• प्रत्येक उपस्ट्रिंग str[i से j] के लिए। vector vec(MAX, 0); इसमें इसमें अंग्रेजी वर्णमालाओं की गिनती होगी।
• वर्तमान वर्ण को c में str[j] के रूप में लें। temp=c-'a' द्वारा इसका पूर्णांक मान लें।
• आवृत्ति को vec[temp]++ द्वारा अपडेट करें।
• mp_vec[vec]++ का उपयोग करके इस आवृत्ति वेक्टर से संबंधित गिनती बढ़ाएं।
• अब सभी आवृत्ति वेक्टर वाले मैप को पार करें और फॉर लूप का उपयोग करके इटरेटर it=mp_vec.begin() से it != mp_vec.end() तक उपस्ट्रिंग गिनती एकत्र करें।
• प्रत्येक गिनती के लिए it->second के रूप में, सभी अनाग्राम युग्मों के लिए ((last) * (last-1))/2 को गिनती में जोड़ें
• अंत में हमारे पास सभी अनाग्राम की गिनती होगी।
• परिणाम के रूप में गिनती वापस करें।

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 
#define MAX 26 

int anagram_substring(string str, int length){ 
    int count = 0; 
    map, int> mp_vec; 
    for (int i=0; i vec(MAX, 0); 
        for (int j=i; jsecond; 
        count += ((last) * (last-1))/2; 
    } 
    return count; 
} 

int main(){ 
    string str = "TP"; 
    int length = str.length(); 
    cout<<"Count of total anagram substrings are: "<<anagram_substring(str, length) << endl; 
    return 0; 
}

आउटपुट

Count of total anagram substrings are: 3