C++ এ সংক্ষিপ্ততম সংখ্যাগরিষ্ঠ সাবস্ট্রিং

ধরুন আমাদের একটি ছোট হাতের বর্ণমালার স্ট্রিং s আছে, আমাদেরকে সবচেয়ে ছোট সাবস্ট্রিংয়ের দৈর্ঘ্য খুঁজে বের করতে হবে (সর্বনিম্ন দৈর্ঘ্য 2) যাতে কিছু অক্ষর মিলিত অন্যান্য অক্ষরের চেয়ে বেশি দেখা যায়। যদি আমরা কোন সমাধান খুঁজে না পাই, তাহলে -1 ফিরে আসুন।

সুতরাং, যদি ইনপুটটি "abbbcde" এর মত হয়, তাহলে আউটপুট হবে 2, সাবস্ট্রিং "bb" এর ন্যূনতম দৈর্ঘ্য রয়েছে এবং এটি অন্যান্য অক্ষরের চেয়ে বেশি দেখায়৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সংজ্ঞায়িত করুন ঠিক আছে(), এটি একটি অ্যারে cnt,

  নেবে

• মোট :=0, maxVal :=0

• প্রতিটি উপাদানের জন্য এটি cnt, করুন

  • মোট :=মোট + এটি

  • maxVal :=সর্বাধিক maxVal এবং এটি

• maxVal> (total - maxVal)

  হলে true রিটার্ন করুন

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• n :=s

  এর আকার

• ret :=inf

• আরম্ভ করার জন্য i :=0, যখন i

  • যদি i + 1

    • রিটার্ন 2

  • অন্যথায় যখন i + 2

    • ret :=3

• রিটার্ন (যদি ret একই হয় inf, তাহলে -1, অন্যথায় ret)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool ok(vector <int>& cnt){
      int total = 0;
      int 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"));
}

ইনপুট

"abbbcde"

আউটপুট

2