ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদেরকে 0 এবং 1 এর সমান সংখ্যক সংলগ্ন সাবস্ট্রিংগুলির গণনা খুঁজে বের করতে হবে এবং এই সাবস্ট্রিংগুলির সমস্ত 0 এবং সমস্ত 1 পরপর গ্রুপ করা হয়েছে। সাবস্ট্রিং একাধিকবার ঘটলে সেগুলি যতবার ঘটবে তার সংখ্যা গণনা করা হয়।
সুতরাং, যদি ইনপুটটি "11001100" এর মত হয়, তাহলে আউটপুট হবে 6, সাবস্ট্রিংগুলি যেমন "1100", "10","0011", "01", "1100", "10"।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- 2 আকারের একটি অ্যারে cnt সংজ্ঞায়িত করুন এবং এটি 0 দিয়ে পূরণ করুন
- res :=0
- আরম্ভ করার জন্য i :=0, যখন i
- সংখ্যা :=s[i] - '0' এর ASCII
- যদি i 0 এর সমান হয় বা s[i] s[i - 1] এর সমান না হয়, তাহলে −
- cnt[num] :=0
- (cnt[num] 1 দ্বারা বাড়ান)
- যদি cnt[num] <=cnt[1 - num] হয়, তাহলে −
- (1 দ্বারা রেজুলেশন বাড়ান)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int countBinarySubstrings(string s) {
int cnt[2] = { 0 };
int res = 0;
for (int i = 0; i < s.length(); ++i) {
int num = s[i] - '0';
if (i == 0 || s[i] != s[i - 1])
cnt[num] = 0;
++cnt[num];
if (cnt[num] <= cnt[1 - num])
++res;
}
return res;
}
};
main(){
Solution ob;
cout << (ob.countBinarySubstrings("11001100"));
} ইনপুট
"11001100"
আউটপুট
6
