पायथन में अधिकतम संख्या में गैर-अतिव्यापी सबस्ट्रिंग खोजने का कार्यक्रम

मान लीजिए कि हमारे पास केवल लोअरकेस अक्षरों वाला एक स्ट्रिंग है, हमें निम्नलिखित नियमों को पूरा करने वाले s के गैर-रिक्त सबस्ट्रिंग की अधिकतम संख्या ज्ञात करनी है

• सबस्ट्रिंग गैर-अतिव्यापी हैं

• एक सबस्ट्रिंग जिसमें एक विशिष्ट वर्ण ch होता है, उसमें ch की सभी आवृत्तियां भी होनी चाहिए।

हमें इन दो शर्तों को पूरा करने वाले सबस्ट्रिंग की अधिकतम संख्या ज्ञात करनी है। यदि समान संख्या में सबस्ट्रिंग वाले ऐसे एक से अधिक समाधान हैं, तो उसे न्यूनतम कुल लंबाई के साथ लौटाएं।

इसलिए, यदि इनपुट s ="pqstpqqprrr" जैसा है, तो आउटपुट ["s", "t", "rrr"] होगा क्योंकि शर्तों को पूरा करने वाले सभी संभावित सबस्ट्रिंग हैं ["pqstpqqqprrr", "pqstpqqp" , "सेंट", "एस", "टी", "आरआरआर"]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• दाएँ:=s के दाईं ओर से सभी व्यक्तिगत वर्ण ch की अनुक्रमणिका स्थिति की सूची को क्रमबद्ध करें

• बाएँ:=वर्णों के सूचकांकों की एक सूची [i] सभी के लिए मैं दाईं ओर

• है:=एक खाली सूची, सामान्य:=एक खाली सूची

• मैं के लिए 0 से लेकर दाएं -1 के आकार की सीमा में हूं, करें

  • gen के अंत में s[right[i]] से वर्णों का एक नया सेट डालें

  • के अंत में s [इंडेक्स (बाएं [i] + 1 से दाएं [i] -1] - जीन का अंतिम आइटम) के सबस्ट्रिंग से वर्णों का एक नया सेट डालें

  • j के लिए रेंज आकार में है - 2 से 0, 1 से घटाएं, करें

    • अगर (है और जीन का अंतिम आइटम [जे]) और (है [जे] और जीन का अंतिम आइटम) शून्य नहीं है, तो

      • जनरल का अंतिम आइटम:=जनरल या जनरल का अंतिम आइटम [j]

      • का अंतिम आइटम है :=( का अंतिम आइटम है या है [j]) - जनरल का अंतिम आइटम

      • निकालें है[j], gen[j]

• रेस:=एक नई सूची, p_right:=-1

• ind के लिए 0 से लेकर हैस - 1 के आकार तक, करें

  • l :=तत्वों की न्यूनतम सूची मैं सभी के लिए मैं बाईं ओर यदि s[i] gen[ind]

    में मौजूद है

  • r :=तत्वों की अधिकतम सूची मैं सभी के लिए मैं सही अगर s[i] gen[ind]]

    में

  • अगर p_right

    • रेस के अंत में s [इंडेक्स l से r तक] का सबस्ट्रिंग डालें

    • p_right:=r

• रिटर्न रेस

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें

def solve(s):
   right = sorted([s.rindex(ch) for ch in set(s)])
   left = [s.index(s[i]) for i in right]
 
   has, gen = [], []
   for i in range(len(right)):
      gen.append(set(s[right[i]]))
      has.append(set(s[left[i] + 1:right[i]]) - gen[-1])

   for j in range(len(has) - 2, -1, -1):
      if (has[-1] & gen[j]) and (has[j] & gen[-1]):
         gen[-1] = gen[-1] | gen[j]
         has[-1] = (has[-1] | has[j]) - gen[-1]
         del has[j], gen[j]

   res, p_right = [], -1
   for ind in range(len(has)):
      l = min([i for i in left if s[i] in gen[ind]])
      r = max([i for i in right if s[i] in gen[ind]])
      if p_right < l:
         res.append(s[l : r + 1])
         p_right = r

   return res

s = "pqstpqqprrr"
print(solve(s))

इनपुट

"pqstpqqprrr"

आउटपुट

['s', 't', 'rrr']