মনে করুন একটি বাইনারি স্ট্রিং এবং একটি ইন্টিজার k আছে। আমাদের চেক করতে হবে স্ট্রিংটি k বিটের বাইনারি সব পারমুটেশন ধারণ করছে কিনা। ধরুন একটি স্ট্রিং "11001" এবং K = 2, তবে এতে k বিটের সব পারমুটেশন থাকতে হবে: (00, 01, 10, 11)। দিয়ে गये স্ট্রিংতে সব পারমুটেশন আছে। তাই এটি একটি বৈধ স্ট্রিং।
বাইনারি স্ট্রিং এবং k-এর মান নিলে চেক করতে হবে বাইনারি সিকোয়েন্সগুলো মেলে কিনা। বাইনারি সিকোয়েন্স k সাইজের। তাই 2^k সংখ্যক ভিন্ন বাইনারি পারমুটেশন থাকবে। k দৈর্ঘ্যের সব বাইনারি পারমুটেশন স্ট্রিং হিসেবে একটি লিস্টে রাখব, তারপর লিস্টের সব এলিমেন্ট দেওয়া স্ট্রিংয়ের সাবস্ট্রিং হিসেবে আছে কিনা চেক করব। যদি লিস্টের সব স্ট্রিংয়ের জন্য true পাওয়া যায়, তবে স্ট্রিংটি বৈধ, অন্যথায় নয়।
উদাহরণ কোড
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<string> binaryPermutations(int k) {
vector<string> list;
int n = 0;
string bin_str = "";
for (int i = 0; i < k; i++) {
bin_str += "0";
}
int limit = pow(2, k);
list.push_back(bin_str);
for (int i = 1; i < limit; i++) {
int j = 0;
while (j <= k) {
if (bin_str[k - 1 - j] == '0') {
bin_str[k - 1 - j] = '1';
break;
} else {
bin_str[k - 1 - j] = '0';
j++;
}
}
list.push_back(bin_str);
}
return list;
}
bool hasAllPermutation(string str, int k) {
vector<string> list = binaryPermutations(k);
for (int i = 0; i < list.size(); i++) {
string substr = list[i];
size_t found = str.find(substr);
if (found == string::npos) {
return false;
}
}
return true;
}
int main() {
int k = 2;
string str = "11001";
if (hasAllPermutation(str, k)) {
cout << "Has All Permutations";
} else {
cout << "Not All Permutations are found";
}
return 0;
}
আউটপুট
Has All Permutations
