C++-এ স্ট্রিং-এ সকল বাইনারি কোড K দৈর্ঘ্যের আছে কিনা চেক

একটি বাইনারি স্ট্রিং s এবং ইন্টিজার k দেওয়া আছে। চেক করতে হবে দৈর্ঘ্য k এর সব বাইনারি কোড (২ᵏ টি) স্ট্রিংয়ের সাবস্ট্রিং হিসেবে আছে কিনা।

ইনপুট: S = "00110110", k = 2 → আউটপুট: true (কোডগুলো: "00","01","10","11" সবই পাওয়া যায়)

সমাধানের ধাপগুলো (স্লাইডিং উইন্ডো + সেট):

একটি সেট v দিয়ে পাওয়া কোডগুলো রাখব
req := 2^k
স্ট্রিং ট্রায়ভার্স করব স্লাইডিং উইন্ডো দিয়ে:
- কারেন্ট উইন্ডো temp মেইনটেইন করব
- যখন উইন্ডো সাইজ k হয়, temp সেটে যোগ করব
- যদি সেটের সাইজ req হয়, true রিটার্ন করব
শেষে false রিটার্ন করব

উদাহরণ

নিচের কোডটি দেখুন −

#include <bits/stdc++.h>
using namespace std;

typedef long long int lli;

class Solution {
public:
    lli fastPow(lli b, lli p) {
        lli ret = 1;
        while (p) {
            if (p & 1)
                ret *= b;
            b *= b;
            p >>= 1;
        }
        return ret;
    }
    bool hasAllCodes(string s, int k) {
        unordered_set<string> v;
        string temp = "";
        lli req = fastPow(2, k);
        for (lli i = 0; i < s.size(); i++) {
            temp += s[i];
            if (i >= k) {
                temp.erase(0, 1);
            }
            if (i >= k - 1) {
                v.insert(temp);
            }
            if ((lli)v.size() == req)
                return true;
        }
        return false;
    }
};

int main() {
    Solution ob;
    cout << (ob.hasAllCodes("00110110", 2));
}

ইনপুট

"00110110",2