C++ এ ন্যূনতম সংখ্যক ব্যাঙ ক্রোকিং

ধরুন আমাদের croakOfFrogs নামক একটি স্ট্রিং আছে, এটি বিভিন্ন ব্যাঙের স্ট্রিং "ক্রোক" এর সংমিশ্রণকে প্রতিনিধিত্ব করে, একাধিক ব্যাঙ একই সময়ে ক্রাক করতে পারে, তাই একাধিক "ক্রোক" মিশ্রিত হয়। প্রদত্ত স্ট্রিং এর সমস্ত ক্রোক শেষ করতে আমাদের বিভিন্ন ব্যাঙের ন্যূনতম সংখ্যা খুঁজে বের করতে হবে।

এখানে একটি বৈধ "ক্রোক" মানে একটি ব্যাঙ 5টি অক্ষর ‘c’, ‘r’, ‘o’, ‘a’, ‘k’ ক্রমিকভাবে তৈরি করছে। একটি ক্রোক শেষ করতে ব্যাঙকে পাঁচটি অক্ষরই তৈরি করতে হবে। যদি স্ট্রিংটি একটি বৈধ "ক্রোক" স্ট্রিং না হয় তাহলে -1 রিটার্ন করুন।

সুতরাং, যদি ইনপুটটি "crcoakroak" এর মত হয়, তাহলে আউটপুট হবে 2 কারণ প্রথম ব্যাঙ "crcoakroak" চিৎকার করতে পারে। দ্বিতীয় ব্যাঙটি পরে চিৎকার করতে পারে "ক্রকোকরোক"।

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

• একটি মানচিত্র m

  সংজ্ঞায়িত করুন

• আকারের একটি অ্যারে ch সংজ্ঞায়িত করুন:5 এটিকে {'c', 'r', 'o', 'a', 'k'

  দিয়ে বরাদ্দ করুন

• temp :=0, ret :=0

• প্রতিটি উপাদানের জন্য c s, do

  • (m[c] 1 দ্বারা বৃদ্ধি করুন)

  • maxVal :=m[ch[0]]

  • আরম্ভ করার জন্য i :=0, যখন i <5, আপডেট করুন (i 1 দ্বারা বাড়ান), −

    • যদি maxVal

      • রিটার্ন -1

    • maxVal :=m[ch[i]]

  • যদি c 'c' এর মত হয়, তাহলে −

    • (1 দ্বারা তাপমাত্রা বাড়ান)

  • অন্যথায় যখন c 'k' এর মত হয়, তখন −

    • (তাপমাত্রা 1 দ্বারা কমান)

  • ret :=সর্বোচ্চ ret এবং temp

• আরম্ভ করার জন্য i :=1, যখন i <5, আপডেট করুন (i 1 দ্বারা বাড়ান), −

  • যদি m[ch[0]] m[ch[i]] এর সমান না হয়, তাহলে −

    • রিটার্ন -1

• রিটার্ন রিটার্ন

উদাহরণ

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minNumberOfFrogs(string s) {
      map<char, int> m;
      char ch[5] = { 'c', 'r', 'o', 'a', 'k' };
      int temp = 0;
      int ret = 0;
      for (auto& c : s) {
         m[c]++;
         int maxVal = m[ch[0]];
         for (int i = 0; i < 5; i++) {
            if (maxVal < m[ch[i]] || m[ch[i]] < 0) {
               return -1;
            }
            maxVal = m[ch[i]];
         }
         if (c == 'c') {
            temp++;
         }
         else if (c == 'k') {
            temp--;
         }
         ret = max(ret, temp);
      }
      for (int i = 1; i < 5; i++) {
         if (m[ch[0]] != m[ch[i]])
            return -1;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.minNumberOfFrogs("crcoakroak"));
}

ইনপুট

"crcoakroak"

আউটপুট

2