Thay thế chuỗi con cho chuỗi cân bằng trong C ++

Giả sử chúng ta có một chuỗi chỉ chứa 4 loại ký tự 'Q', 'W', 'E' và 'R'. Một chuỗi sẽ được cân bằng nếu mỗi ký tự của nó xuất hiện n / 4 lần trong đó n là độ dài của chuỗi. Tìm độ dài nhỏ nhất của chuỗi con có thể được thay thế bằng bất kỳ chuỗi nào khác có cùng độ dài để chuỗi ban đầu được cân bằng. Vì vậy, nếu s =“QQWE”, thì đầu ra sẽ là 1. Điều này là do chúng ta có thể thay thế Q thành R, để “RQWE”, được cân bằng.

Trả về 0 nếu chuỗi đã được cân bằng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo một bản đồ m
• đối với mỗi ký tự tính bằng s, lưu trữ tần số ký tự vào bản đồ, n:=kích thước của s
• res:=n, left:=0
• cho bên phải trong phạm vi 0 đến n - 1
  • giảm m [s [right]] đi 1
  • khi bên trái
  • res:=tối thiểu res, phải - trái + 1
  • tăng m [s [left]] lên 1
  • tăng bên trái 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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"));
}

Đầu vào

"QQEQ"

Đầu ra

2