C++ এ তিনটি অক্ষর সমন্বিত সাবস্ট্রিংয়ের সংখ্যা

ধরুন আমরা একটি স্ট্রিং দিয়েছি যা শুধুমাত্র a, b এবং c অক্ষর নিয়ে গঠিত। আমাদের এই সমস্ত অক্ষর a, b এবং c এর কমপক্ষে একটি উপস্থিতি ধারণকারী সাবস্ট্রিংগুলির সংখ্যা ফেরত দিতে হবে। উদাহরণস্বরূপ, যদি স্ট্রিংটি "abcabc" হয়, তাহলে আউটপুট হবে 10, কারণ সাবস্ট্রিংটিতে a, b এবং c অক্ষরের অন্তত একটি উপস্থিতি রয়েছে, এইগুলি হল "abc", "abca", "abcab", “abcabc”, “bca”, “bcab”, “cab”, “cabc” এবং “abc” (আবার শেষ অংশের জন্য)।

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

• ret :=0, m নামে একটি মানচিত্র তৈরি করুন, j :=0

  সেট করুন

• i এর জন্য 0 থেকে s আকারের সীমার মধ্যে

  • m

    ম্যাপে s[i] এর সংখ্যা বাড়ান

  • যখন m[‘a’]> 0 এবং m[‘b’]> 0 এবং m[‘c’]> 0,

    • m

      মানচিত্রে s[i] এর গণনা হ্রাস করুন

    • 1 দ্বারা j বাড়ান

  • j দ্বারা ret বাড়ান

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

উদাহরণ (C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numberOfSubstrings(string s) {
      int ret = 0;
      map <char, int> m;
      int j = 0;
      for(int i = 0; i < s.size(); i++){
         m[s[i]]++;
         while(m['a'] > 0 && m['b'] > 0 && m['c'] > 0){
            m[s[j]]--;
            j++;
         }
         ret += j;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.numberOfSubstrings("abcabc"));
}

ইনপুট

"abcabc"

আউটপুট

10