मान लीजिए हमारे पास स्ट्रिंग्स की एक सूची है; हमें उनमें से सबसे लंबी असामान्य उपअनुक्रम ढूंढना है। सबसे लंबी असामान्य उपअनुक्रम वास्तव में इन स्ट्रिंग्स में से एक का सबसे लंबा उपअनुक्रम है और यह उपअनुक्रम अन्य किसी स्ट्रिंग का उपअनुक्रम नहीं होना चाहिए।
हम जानते हैं कि एक उपअनुक्रम एक अनुक्रम है जिसे किसी अन्य अनुक्रम से कुछ वर्णों को हटाकर, शेष तत्वों के क्रम को बदले बिना प्राप्त किया जा सकता है।
यहां हम स्ट्रिंग्स की एक सूची लेंगे, और आउटपुट सबसे लंबी असामान्य उपअनुक्रम की लंबाई होनी चाहिए। यदि ऐसी कोई उपअनुक्रम नहीं है, तो -1 लौटाएं।
उदाहरण के लिए, यदि इनपुट "aba", "cdc", "eae" है, तो आउटपुट 3 होगा।
हल करने की विधि
हम निम्न चरणों का पालन करेंगे:
isSubsequence()फ़ंक्शन परिभाषित करें, जो जांचता है कि क्या स्ट्रिंग b, स्ट्रिंग a का उपअनुक्रम है।getDuplicates()फ़ंक्शन परिभाषित करें, जो डुप्लिकेट स्ट्रिंग्स का सेट लौटाता है।- मुख्य विधि में:
- स्ट्रिंग्स को लंबाई के अवरोही क्रम में सॉर्ट करें।
- डुप्लिकेट सेट प्राप्त करें।
- प्रत्येक स्ट्रिंग के लिए, यदि यह डुप्लिकेट है तो छोड़ दें।
- यदि यह पहली स्ट्रिंग है (सबसे लंबी), तो इसकी लंबाई लौटाएं।
- अन्यथा, जांचें कि क्या यह किसी पिछली स्ट्रिंग का उपअनुक्रम नहीं है। यदि यह किसी का उपअनुक्रम नहीं है, तो इसकी लंबाई लौटाएं।
- यदि कोई नहीं मिला, तो -1 लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class Solution { public: static bool cmp(string a, string b){ return a.size() > b.size(); } int findLUSlength(vector<string>& strs){ sort(strs.begin(), strs.end(), cmp); set<string> duplicates = getDuplicates(strs); for (int i = 0; i < strs.size(); i++) { if (duplicates.count(strs[i])) continue; if (i == 0) return strs[i].size(); for (int j = 0; j < i; j++) { if (!isSubsequence(strs[j], strs[i])) { if ((j == i - 1)) { cout << i << endl; return strs[i].size(); } } else break; } } return -1; } bool isSubsequence(string a, string b){ int j = 0; for (int i = 0; i < a.size(); i++) { if (j < b.size() && a[i] == b[j]) j++; } return j == b.size(); } set<string> getDuplicates(vector<string>& strs){ set<string> visited; set<string> ret; for (int i = 0; i < strs.size(); i++) { if (visited.count(strs[i])) { ret.insert(strs[i]); } visited.insert(strs[i]); } return ret; } }; main(){ Solution ob; vector<string> v = {"aba", "cdc", "eae"}; cout << (ob.findLUSlength(v)); }
इनपुट
{"aba", "cdc", "eae"}
आउटपुट
3
