ধরুন একটি স্ট্রিং s দেওয়া আছে যেটি শুধু a, b, c ক্যারেক্টার দিয়ে গঠিত। আমাদের সাবস্ট্রিংগুলোর সংখ্যা বের করতে হবে যেগুলো কমপক্ষে একবার a, b, c তিনों ক্যারেক্টার ধারণ করে। উদাহরণস্বরূপ, স্ট্রিং “abcabc” হলে আউটপুট ১০, কারণ a, b, c ধারণকারী সাবস্ট্রিংগুলো: “abc”, “abca”, “abcab”, “abcabc”, “bca”, “bcab”, “cab”, “cabc” এবং “abc” (শেষ অংশের জন্য আবার)।
সমাধানের ধাপগুলো:
ret := 0, একটি map m তৈরি করুন, j := 0 সেট করুন
i = 0 থেকে s-এর সাইজ পর্যন্ত লুপ চালান
m-এ s[i]-এর কাউন্ট বাড়ান
যখন m['a'] > 0 এবং m['b'] > 0 এবং m['c'] > 0
m-এ s[j]-এর কাউন্ট কমান
j ১ বাড়ান
ret += 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
