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

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

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

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

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

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

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

• right := s के दाएं से सभी व्यक्तिगत वर्ण ch की सूचकांक स्थिति की क्रमबद्ध सूची

• left := right में सभी i के लिए s[i] के वर्णों के सूचकांकों की एक सूची

• has := एक खाली सूची, gen := एक खाली सूची

• i को 0 से right के आकार - 1 तक के लिए, करें

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

  • s के उपस्ट्रिंग [left[i] + 1 से right[i]-1] के वर्णों का एक नया सेट - gen का अंतिम आइटम, has के अंत में डालें

  • j को has के आकार - 2 से 0 तक, 1 से घटाकर, करें

    • यदि (has का अंतिम आइटम AND gen[j]) और (has[j] AND gen का अंतिम आइटम) शून्येतर है, तो

      • gen का अंतिम आइटम := gen का अंतिम आइटम OR gen[j]

      • has का अंतिम आइटम := (has का अंतिम आइटम OR has[j]) - gen का अंतिम आइटम

      • has[j], gen[j] हटाएं

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

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

  • l := उन सभी i का न्यूनतम जिनके लिए s[i], gen[ind] में मौजूद है

  • r := उन सभी i का अधिकतम जिनके लिए s[i], gen[ind] में है

  • यदि p_right < l, तो

    • s के उपस्ट्रिंग [l से r] को res के अंत में डालें

    • p_right := r

• res वापस करें

उदाहरण

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

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']