मान लीजिए हमारे पास स्ट्रिंग्स की एक सरणी arr है। स्ट्रिंग s, arr के एक उप-अनुक्रम का संयोजन है जिसमें अद्वितीय वर्ण हैं। s की अधिकतम संभव लंबाई ढूंढें। यदि इनपुट ["cha", "r", "act", "ers"] जैसा है, तो आउटपुट 6 होगा, संभावित समाधान "chaers" और "acters" हैं।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
ok()नामक एक विधि बनाएं जो स्ट्रिंग्सsऔरtलेगी। यह निम्नानुसार कार्य करेगी:xनामक एक मैप बनाएंiको 0 सेsके आकार तक लूप करेंx[s[i]]को 1 से बढ़ाएं- यदि
x[s[i]] > 1, तो गलत लौटाएं
iको 0 सेtके आकार तक लूप करेंx[t[i]]को 1 से बढ़ाएं- यदि
x[t[i]] > 1, तो गलत लौटाएं
- सही लौटाएं
- वास्तविक विधि निम्नानुसार दिखेगी:
vनामक स्ट्रिंग्स की एक सरणी बनाएं, औरans := 0,vमें एक खाली स्ट्रिंग डालेंiको 0 सेarrके आकार तक लूप करेंn := v का आकारjको 0 सेn - 1तक लूप करें- यदि
ok(v[j], arr[i])सही है, तोt := v[j] + arr[i]tकोvमें डालेंans := ans और t के आकार का अधिकतम
- यदि
ansलौटाएं
उदाहरण
#include <bits/stdc++.h> using namespace std; class Solution { public: bool ok(string s, string t){ map <char, int > x; for(int i = 0; i < s.size(); i++){ x[s[i]]++; if(x[s[i]] >1)return false; } for(int i = 0; i < t.size(); i++){ x[t[i]]++; if(x[t[i]]>1)return false; } return true; } int maxLength(vector<string>& arr) { vector <string> v; int ans = 0; v.push_back(""); for(int i = 0; i < arr.size(); i++){ int n = v.size(); for(int j = 0; j < n; j++){ if(ok(v[j],arr[i])){ string t = v[j]+arr[i]; v.push_back(t); ans = max(ans,(int)t.size()); } } } return ans; } }; main(){ vector<string> v = {"cha","r","act","ers"}; Solution ob; cout << (ob.maxLength(v)); }इनपुट
["cha","r","act","ers"]
आउटपुट
6
