ধরুন আমাদের একটি স্ট্রিং s এবং একটি সংখ্যা k আছে। আমাদের s-এর সমস্ত অক্ষর ব্যবহার করে k অ-খালি প্যালিনড্রোম স্ট্রিংগুলি তৈরি করতে হবে। সুতরাং এখানে আমাদের পরীক্ষা করতে হবে যে আমরা k প্যালিনড্রোম স্ট্রিংগুলি তৈরি করতে s-এর সমস্ত অক্ষর ব্যবহার করতে পারি কিনা৷
সুতরাং, যদি ইনপুটটি "true", k =4 এর মত হয়, তাহলে আউটপুটটি True হবে, কারণ একমাত্র সম্ভাব্য সমাধান হল প্রতিটি অক্ষরকে একটি পৃথক স্ট্রিংয়ে রাখা।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=s
এর আকার -
যদি n
-
মিথ্যা ফেরত দিন
-
-
যদি n হয় k এর মত, তাহলে −
-
প্রত্যাবর্তন সত্য
-
-
একটি মানচিত্র সংজ্ঞায়িত করুন
-
প্রতিটি অক্ষরের জন্য c s
-
(m[c] 1 দ্বারা বৃদ্ধি করুন)
-
-
বিজোড় :=0
-
প্রতিটি কী-মানের জন্য এটিকে m −
-এ যুক্ত করুন-
বিজোড় :=বিজোড় + (এর মান এবং ১)
-
-
বিজোড় <=k, অন্যথায় মিথ্যা
হলে true ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canConstruct(string s, int k) {
int n = s.size();
if (n < k)
return false;
if (n == k)
return true;
map<char, int> m;
for (char c : s)
m[c]++;
int odd = 0;
for (auto& it : m) {
odd += (it.second & 1);
}
return odd <= k;
}
};
main(){
Solution ob;
cout << (ob.canConstruct("true",4));
} ইনপুট
"true"
আউটপুট
1
