मान लीजिए हमारे पास एक स्ट्रिंग है जिसमें केवल 4 प्रकार के वर्ण 'Q', 'W', 'E' और 'R' हैं। एक स्ट्रिंग संतुलित होगी यदि उसका प्रत्येक वर्ण n/4 बार प्रकट होता है जहाँ n स्ट्रिंग की लंबाई है। सबस्ट्रिंग की न्यूनतम लंबाई ज्ञात करें जिसे मूल स्ट्रिंग को संतुलित करने के लिए समान लंबाई के किसी भी अन्य स्ट्रिंग के साथ प्रतिस्थापित किया जा सकता है। तो अगर s ="QQWE", तो आउटपुट 1 होगा। ऐसा इसलिए है क्योंकि हम Q को R से बदल सकते हैं, ताकि "RQWE", जो संतुलित हो।
यदि स्ट्रिंग पहले से ही संतुलित है तो 0 लौटाएं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक नक्शा मी बनाएं
- s में प्रत्येक वर्ण के लिए, वर्णों की आवृत्ति को मानचित्र में संग्रहीत करें, n :=s का आकार
- res :=n, लेफ्ट :=0
- 0 से n - 1 की सीमा में दाएं के लिए
- m[s[right]] को 1 से कम करें
- बाएं
- res :=न्यूनतम रेस, दाएं-बाएं + 1
- m[s[बाएं]] को 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