ধরুন আমাদের একটি স্ট্রিং আছে যেখানে মাত্র 4 ধরনের অক্ষর রয়েছে 'Q', 'W', 'E' এবং 'R'। একটি স্ট্রিং ভারসাম্যপূর্ণ হবে যদি এর প্রতিটি অক্ষর n/4 বার প্রদর্শিত হয় যেখানে n স্ট্রিংটির দৈর্ঘ্য। মূল স্ট্রিংটিকে সুষম করতে একই দৈর্ঘ্যের অন্য কোনো স্ট্রিং দিয়ে প্রতিস্থাপন করা যেতে পারে এমন সাবস্ট্রিংটির ন্যূনতম দৈর্ঘ্য খুঁজুন। সুতরাং যদি s =“QQWE” হয়, তাহলে আউটপুট হবে 1। এর কারণ হল আমরা Q থেকে R প্রতিস্থাপন করতে পারি, যাতে “RQWE”, যেটি ভারসাম্যপূর্ণ হয়।
যদি স্ট্রিংটি ইতিমধ্যেই ভারসাম্যপূর্ণ থাকে তাহলে 0 ফেরত দিন।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি মানচিত্র তৈরি করুন m
- s-এর প্রতিটি অক্ষরের জন্য, ম্যাপে অক্ষরের ফ্রিকোয়েন্সি সংরক্ষণ করুন, n :=s-এর আকার
- res :=n, left :=0
- 0 থেকে n – 1
- পরিসরের অধিকারের জন্য
- m[s[ডানে]] 1 কমিয়ে দিন
- বামে থাকাকালীন
- res :=ন্যূনতম রেস, ডান – বাম + 1
- m[s[left]] 1 দ্বারা বাড়ান
- বামে 1 বাড়ান
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int balancedString(string s) {
unordered_map <char, int> m;
for(int i = 0;i<s.size();i++)m[s[i]]++;
int n = s.size();
int res = n;
int left = 0;
for(int right = 0;right<n;right++){
m[s[right]]--;
while(left<n && m['Q']<=n/4 && m['W'] <=n/4 && m['E'] <=n/4 && m['R']<=n/4){
res = min(res, right - left + 1);
m[s[left]]+=1;
left++;
}
}
return res;
}
};
main(){
Solution ob;
cout << (ob.balancedString("QQEQ"));
} ইনপুট
"QQEQ"
আউটপুট
2
