C++ का उपयोग करके इनपुट स्ट्रिंग में अधिकतम घटित होने वाला वर्ण खोजना

समस्या विवरण

इस समस्या में, हमें लोअरकेस वर्णों की एक इनपुट स्ट्रिंग दी गई है। हमारा कार्य इनपुट स्ट्रिंग में अधिकतम घटित होने वाला वर्ण खोजना है।

समान आवृत्ति वाले एकाधिक मानों के मामले में, हमें लेक्सिकोग्राफिक रूप से छोटे मान को प्रिंट करने की आवश्यकता है।

उदाहरण

इनपुट

string = "programming"

आउटपुट

g

व्याख्या: 'g' और 'm' दोनों 2 बार आते हैं, लेकिन 'g' लेक्सिकोग्राफिक रूप से छोटा है।

हल का दृष्टिकोण

समस्या का समाधान खोजने के लिए, हमें दी गई स्ट्रिंग को क्रमबद्ध करने की आवश्यकता है और फिर स्ट्रिंग को पार करना है ताकि हम उस वर्ण को खोज सकें जिसकी स्ट्रिंग में अधिकतम घटना है। हम इस समस्या को जीतने के लिए हैशिंग विधि (हैश टेबल विधि) का उपयोग करेंगे। प्रत्येक व्यक्तिगत वर्ण को वर्णों की सरणी में पार करना और हैश करना हैशिंग कहलाता है।

आमतौर पर, हैश सरणी का आकार 256 आवंटित किया जाता है। लेकिन यदि स्ट्रिंग में केवल 0 से 127 तक के वर्ण हैं तो हम आकार 128 की हैश टेबल का उपयोग कर सकते हैं, ताकि हम स्ट्रिंग के अनुसार हैश टेबल आकार को डिएलोकेट कर सकें।

एल्गोरिदम

1. एक इनपुट स्ट्रिंग पढ़ें
2. स्ट्रिंग में अधिकतम घटित होने वाले वर्ण की गणना करने के लिए एक फंक्शन बनाएं
3. व्यक्तिगत वर्णों की गिनती रखने के लिए एक सरणी बनाएं और सरणी को 0 से प्रारंभ करें
4. इनपुट स्ट्रिंग से वर्ण गिनती सरणी बनाएं
5. अधिकतम गिनती और परिणाम प्रारंभ करें
6. स्ट्रिंग के माध्यम से पार करें और प्रत्येक की गिनती बनाए रखें
7. अंत में, अधिकतम गिनती वाले वर्ण को खोजें और इसे प्रिंट करें

C++ कार्यान्वयन

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

char findMaxOccuringChar(char str[]) {
    int freq[26] = {0};
    int maxFreq = -1;
    char maxFreqChar;
    int len = strlen(str);
    
    for (int i = 0; i < len; i++)
        freq[str[i] - 'a']++;
    
    for (int i = 0; i < 26; i++) {
        if (maxFreq < freq[i]) {
            maxFreq = freq[i];
            maxFreqChar = (char)(i + 'a');
        }
    }
    
    return maxFreqChar;
}

int main() {
    char str[] = "programming";
    cout << "इनपुट स्ट्रिंग का अधिकतम घटित होने वाला वर्ण है " << findMaxOccuringChar(str);
    return 0;
}

आउटपुट

इनपुट स्ट्रिंग का अधिकतम घटित होने वाला वर्ण है g

जटिलता विश्लेषण

• समय जटिलता: O(N) जहां N स्ट्रिंग की लंबाई है
• स्पेस जटिलता: O(1) - निश्चित आकार 26 सरणी

टिप्पणी

कोड लोअरकेस अंग्रेजी अक्षरों के लिए मानता है। सामान्य ASCII के लिए, आकार 256 की सरणी का उपयोग करें। टाई-ब्रेकिंग स्वाभाविक रूप से काम करती है क्योंकि हम 'a' से 'z' तक पुनरावृति करते हैं और केवल सख्ती से बड़ी गिनती पर अपडेट करते हैं।