จำนวนสูงสุดของสตริงย่อยใน C++

สมมติว่าเรามีสตริง s เราต้องหาจำนวนสูงสุดของสตริงย่อยที่เป็นไปตามกฎต่อไปนี้ -

• จำนวนอักขระที่ไม่ซ้ำในสตริงย่อยต้องน้อยกว่าหรือเท่ากับ maxLetters
• ขนาดสตริงย่อยต้องอยู่ในช่วง minSize และ maxSize รวมอยู่ด้วย

ดังนั้น หากอินพุตเป็น − “aababcaab”, maxLetters =2, minSize =3 และ maxSize =4 ผลลัพธ์จะเป็น 2 สตริงย่อย "aab" มี 2 รายการในสตริงดั้งเดิม ซึ่งเป็นไปตามเงื่อนไข ตัวอักษร 2 ตัวที่ไม่ซ้ำกันและขนาด 3 (ระหว่าง minSize และ maxSize)

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดแผนที่ m
• สำหรับ sz ในช่วง minSize ถึง maxSize
  • สร้างแผนที่ x สร้าง temp เริ่มแรกว่างเปล่า
  • สำหรับฉันอยู่ในช่วง 0 ถึง sz – 1
    • เพิ่ม x[s[i]] ขึ้น 1
    • อุณหภูมิ :=อุณหภูมิ + s[i]
  • สำหรับ j คือ 0, i ในช่วง sz ถึงขนาด s – 1 ให้เพิ่ม i และ j ขึ้น 1
    • ถ้าขนาด x <=maxLetters ให้เพิ่ม m[temp] ขึ้น 1
    • ลด x[temp[0]] ขึ้น 1
    • ถ้า x[temp[0]] เป็น 0 ให้ลบ temp[0] ออกจาก x
    • ลบองค์ประกอบ temp แรกและตัวที่สองออกจากตัว temp เอง
    • เพิ่ม x[s[i]] ขึ้น 1
    • อุณหภูมิ :=อุณหภูมิ + s[i]
  • ถ้าขนาด x <=maxLetters ให้เพิ่ม m[temp] ขึ้น 1
• ตอบ :=0
• ในขณะที่ map m มีองค์ประกอบบางอย่างแล้ว
  • ans :=สูงสุดของ ans และค่าของคู่คีย์-ค่า ith
• คืนสินค้า

ตัวอย่าง(C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
      unordered_map <string ,int > m;
      for(int sz = minSize; sz <= minSize; sz++){
         unordered_map <char, int> x;
         string temp ="";
         for(int i = 0; i < sz; i++){
            x[s[i]]++;
            temp += s[i];
         }
         for(int j = 0, i = sz; i < s.size(); i++, j++){
            if(x.size() <= maxLetters){
               m[temp]++;
            }
            x[temp[0]]--;
            if(x[temp[0]] == 0)x.erase(temp[0]);
            temp.erase(temp.begin(),temp.begin() + 1);
            x[s[i]]++;
            temp += s[i];
         }
         if(x.size() <= maxLetters){
            m[temp]++;
         }
      }
      int ans = 0;
      unordered_map <string ,int > :: iterator i = m.begin();
      while(i != m.end()){
         ans = max (ans, i->second);
         i++;
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.maxFreq("aababcaab",2,3,4));
}

อินพุต

"aababcaab"
2
3
4

ผลลัพธ์

2