C++ में संतुलित स्ट्रिंग के लिए उपस्ट्रिंग बदलें

मान लीजिए हमारे पास केवल 4 प्रकार के वर्णों 'Q', 'W', 'E' और 'R' वाली एक स्ट्रिंग है। एक स्ट्रिंग संतुलित होगी यदि इसके प्रत्येक वर्ण n/4 बार प्रकट होते हैं जहां n स्ट्रिंग की लंबाई है। उस उपस्ट्रिंग की न्यूनतम लंबाई ढूंढें जिसे समान लंबाई की किसी अन्य स्ट्रिंग से बदला जा सकता है ताकि मूल स्ट्रिंग संतुलित हो जाए।

उदाहरण के लिए, यदि s = "QQWE", तो आउटपुट 1 होगा। ऐसा इसलिए है क्योंकि हम Q को R से बदल सकते हैं, ताकि "RQWE" बने, जो संतुलित है।

यदि स्ट्रिंग पहले से ही संतुलित है तो 0 लौटाएं।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

m नामक एक मैप बनाएं
s में प्रत्येक वर्ण के लिए, वर्णों की आवृत्ति को मैप में संग्रहीत करें, n := s का आकार
res := n, left := 0
right को 0 से n - 1 तक लूप करें
- m[s[right]] को 1 से घटाएं
- जब तक left < n और m['Q'] <= n/4 और m['W'] <= n/4 और m['E'] <= n/4 और m['R'] <= n/4
  - res := res और (right - left + 1) का न्यूनतम
  - m[s[left]] को 1 से बढ़ाएं
  - left को 1 से बढ़ाएं
res लौटाएं

उदाहरण

#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"