C++-এ শর্টেস্ট মেজোরিটি সাবস্ট্রিং (Shortest Majority Substring) বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি লোয়ারকেস স্ট্রিং s দেওয়া থাকলে, ন্যূনতম দৈর্ঘ্যের সাবস্ট্রিং (দৈর্ঘ্য কমপক্ষে ২) বের করুন যাতে কোনো এক ক্যারেক্টার অন্য সব ক্যারেক্টার মিলিত চেয়ে বেশি বার আসে। না পাওয়া গেলে -1 রিটার্ন করুন।

উদাহরণ: "abbbcde" → "bb" (দৈর্ঘ্য ২) → আউটপুট ২।

সমাধানের পদ্ধতি (Observation-based)

1. দৈর্ঘ্য ২ এর সাবস্ট্রিং চেক করুন: যদি s[i] == s[i+1] হয়, তবে উত্তর ২ (কারণ ২টি একই ক্যারেক্টার → মেজোরিটি)।
2. দৈর্ঘ্য ৩ এর সাবস্ট্রিং চেক করুন: যদি s[i] == s[i+2] হয়, তবে উত্তর ৩ (যেমন "aba")।
3. দৈর্ঘ্য ৪ বা বেশি চেক করার দরকার নেই, কারণ দৈর্ঘ্য ২ বা ৩ না পাওয়া মানে বড় দৈর্ঘ্যও পাওয়া যাবে না (প্রমাণ করা যায়)।

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;
}

আউটপুট

2

জটিলতা

• সময়: O(n)
• স্থান: O(1)