मान लीजिए कि हमारे पास एक स्ट्रिंग s और एक संख्या k है। हमें s में सभी वर्णों का उपयोग करके k गैर-रिक्त पैलिंड्रोम स्ट्रिंग्स का निर्माण करना है। इसलिए यहां हमें यह जांचना होगा कि क्या हम k पैलिंड्रोम स्ट्रिंग्स के निर्माण के लिए s के सभी वर्णों का उपयोग कर सकते हैं या नहीं।
इसलिए, यदि इनपुट "सत्य", k =4 जैसा है, तो आउटपुट ट्रू होगा, क्योंकि प्रत्येक वर्ण को एक अलग स्ट्रिंग में रखना एकमात्र संभव समाधान है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=s का आकार
-
यदि n
-
झूठी वापसी
-
-
यदि n, k के समान है, तो -
-
सही लौटें
-
-
एक मानचित्र परिभाषित करें
-
प्रत्येक वर्ण c के लिए s
-
(m[c] 1 से बढ़ाएं)
-
-
विषम :=0
-
प्रत्येक की-वैल्यू पेयर के लिए इसे m -
. में जोड़ें-
विषम :=विषम + (इसका मान और 1)
-
-
विषम <=k, अन्यथा असत्य होने पर सत्य लौटें
उदाहरण
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#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