Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सबसे छोटा बहुसंख्यक उपस्ट्रिंग (Shortest Majority Substring)


लोअरकेस स्ट्रिंग s दी गई है। न्यूनतम लंबाई (कम से कम 2) का उपस्ट्रिंग ढूंढें जिसमें कोई वर्ण अन्य सभी वर्णों के योग से अधिक बार आता हो। ऐसा न होने पर -1 वापस करें।

मुख्य अवलोकन: उत्तर केवल 2 या 3 हो सकता है। लंबाई 2: दो समान आसन्न वर्ण (जैसे "aa")। लंबाई 3: पैटर्न "aba"।

उदाहरण: "abbbcde" → "bb" लंबाई 2 → आउटपुट 2।

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

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

class Solution {
public:
    bool ok(vector& cnt) {
        int total = 0, maxVal = 0;
        for (auto& it : cnt) { total += it; maxVal = max(maxVal, it); }
        return maxVal > (total - maxVal);
    }
    int solve(string s) {
        int n = s.size();
        int ret = INT_MAX;
        for (int i = 0; i < n; i++) {
            if (i + 1 < n && s[i] == s[i + 1]) return 2;
            else if (i + 2 < n && s[i] == s[i + 2]) ret = 3;
        }
        return ret == INT_MAX ? -1 : ret;
    }
};

int main() {
    Solution ob;
    cout << ob.solve("abbbcde");
    return 0;
}

इनपुट

"abbbcde"

आउटपुट

2
  1. - C++ में दोहराए गए उपस्ट्रिंग पैटर्न (Repeated Substring Pattern)

    मान लीजिए हमारे पास एक गैर-खाली स्ट्रिंग है। हमें जांचना है कि क्या इसे इसके एक उपस्ट्रिंग को लेकर और उपस्ट्रिंग को कई बार जोड़कर बनाया जा सकता है। स्ट्रिंग में केवल लोअरकेस अंग्रेजी अक्षर होते हैं और इसकी लंबाई 10000 से अधिक नहीं होगी। इसलिए यदि इनपुट abaabaaba जैसा है, तो उत्तर true होगा, क्योंकि

  1. - C++ में बहुमत तत्व

    7/2। हम ऐरे में x की घटनाओं को गिन सकते हैं, और यदि संख्या n/2 से अधिक है, तो उत्तर सत्य होगा, अन्यथा असत्य। उदाहरण (C++) #include <iostream> #include <stack> using namespace std; bool isMajorityElement(int arr[], int n, int x){ int freq = 0; for(int i = 0; i n/2); }

  1. - C++ में सबस्ट्रिंग

    सबस्ट्रिंग एक स्ट्रिंग का हिस्सा है। C++ में सबस्ट्रिंग प्राप्त करने के लिए एक फ़ंक्शन substr() है। इस फ़ंक्शन में दो पैरामीटर्स होते हैं: pos और len। pos पैरामीटर सबस्ट्रिंग की शुरुआती पोजीशन निर्दिष्ट करता है और len सबस्ट्रिंग में कैरेक्टर्स की संख्या दर्शाता है। उदाहरण #include <iostream>