แทนที่สตริงย่อยสำหรับสตริงที่สมดุลใน C ++

สมมติว่าเรามีสตริงที่มีอักขระเพียง 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[right]] ลง 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"