สตริงย่อยหน้าต่างขั้นต่ำใน C++

สมมติว่าเรามีสตริง S และ T เราต้องหาหน้าต่างขั้นต่ำใน S ซึ่งจะมีอักขระทั้งหมดใน T ดังนั้นหากอินพุตเป็นเหมือน “ABHDAXCVBAGTXATYCB” และ T =“ABC” ผลลัพธ์จะเป็น:“ CVBA”.

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

• สร้างหนึ่งแผนที่ m

• เก็บความถี่ของ x เป็น m

• length :=ขนาดของ s, left :=0, right :=0, ansLeft :=0 and ansRight :=0

• ตัวนับ :=ขนาดของ x, แฟล็ก :=false, ans :=สตริงว่าง

• ในขณะที่ส่วนสูง <ขนาดของ s −

  • ค :=s[ขวา]

  • ถ้า c มีอยู่ใน m แล้ว

    • ถ้า m[c]> 0 ให้ลดตัวนับลง 1

    • ลด m[c] ลง 1

  • ในขณะที่เคาน์เตอร์ =0 และซ้าย <=ขวา

    • ถ้าขวา – ซ้าย + 1 <=ความยาว

      • ความยาว :=ขวา – ซ้าย + 1

      • ธง :=จริง

      • ansLeft :=ซ้าย ansRight :=ขวา

    • ถ้าซ้าย =ขวา ให้ตัดวงจร

    • c :=s[ซ้าย]

    • ถ้า c มีอยู่ใน m ให้เพิ่ม m[c] ขึ้น 1

    • ถ้า m[c]> 0 ให้เพิ่มตัวนับขึ้น 1

    • เพิ่มขึ้น 1

  • เพิ่มสิทธิ์ 1

• ถ้าแฟล็กเป็นเท็จ ให้คืนค่า ans

• มิฉะนั้นสำหรับฉันในช่วง ansLeft ถึง ansRight ให้เพิ่ม ans โดย s[i]

• กลับมาอีกครั้ง

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string minWindow(string s, string x) {
      map <char, int> m;
      for(int i =0;i<x.size();i++)m[x[i]]++;
      int length = s.size();
      int left = 0, right = 0 , ansLeft = 0, ansRight = 0;
      int counter = x.size();
      bool flag = false;
      string ans = "";
      while(right<s.size()){
         char c = s[right];
         if(m.find(c)!=m.end()){
            if(m[c]>0)counter--;
            m[c]--;
         }
         while(counter == 0 && left<=right){
            if(right-left+1 <=length){
               length = right-left+1;
               flag = true;
               ansLeft = left;
               ansRight = right;
            }
            if(left == right)break;
            c = s[left];
            if(m.find(c)!=m.end()){
               m[c]++;
               if(m[c]>0)counter++;
            }
            left++;
         }
         right++;
      }
      if(!flag)return ans;
      else
      for(int i =ansLeft;i<=ansRight;i++)ans+=s[i];
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.minWindow("ABHDAXCVBAGTXATYCB", "ABC"));
}

อินพุต

"ABHDAXCVBAGTXATYCB"
"ABC"

ผลลัพธ์

CVBA