पायथन में उन सभी सबस्ट्रिंग्स को ढूंढना जिनके एनाग्राम स्ट्रिंग में मौजूद हैं

मान लीजिए हमारे पास लोअरकेस अक्षरों की एक स्ट्रिंग s है। हमें ss में एक अलग स्थान पर कोई अन्य सबस्ट्रिंग हो जो उस लिए गए सबस्ट्रिंग का एनाग्राम हो। हमें लेक्सिकोग्राफिक ऑर्डर में सबस्ट्रिंग्स की एक लिस्ट ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है s = "abcba", तो आउटपुट होगा ['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba', 'bc', 'bcba', 'cb', 'cba'] क्योंकि उनमें से प्रत्येक के लिए हम स्ट्रिंग में ही अलग एनाग्राम ढूंढ सकते हैं।

समाधान दृष्टिकोण

सभी संभावित सबस्ट्रिंग लंबाई के लिए, सभी सबस्ट्रिंग्स को उनके सॉर्टेड रूप (फिंगरप्रिंट) द्वारा समूहित करें। जिन समूहों का आकार >= 2 है, उनके सभी सदस्यों को परिणाम में जोड़ें।

• res खाली लिस्ट से आरंभ करें।
• प्रत्येक लंबाई i 1 से L तक के लिए:
  • सॉर्टेड सबस्ट्रिंग -> मूल सबस्ट्रिंग्स की लिस्ट का मैप smap बनाएं।
  • प्रत्येक प्रारंभ इंडेक्स j के लिए, सबस्ट्रिंग s[j:j+i] निकालें, इसे सॉर्ट करके कुंजी के रूप में उपयोग करें।
  • प्रत्येक कुंजी के लिए जिसके >= 2 मान हैं, उन सभी को res में जोड़ें।
• सॉर्टेड res लौटाएं।

पायथन कार्यान्वयन

from collections import defaultdict

def solve(s):
    res = []
    L = len(s)
    for i in range(1, L + 1):
        smap = defaultdict(list)
        for j in range(L - i + 1):
            cs = s[j : j + i]
            k = "".join(sorted(cs))
            smap[k].append(cs)
        for k, v in smap.items():
            if len(v) >= 2:
                res.extend(v)
    return sorted(res)

s = "abcba"
print(solve(s))

इनपुट

"abcba"

आउटपुट

['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba', 'bc', 'bcba', 'cb', 'cba']