पायथन में स्ट्रिंग के हर सबस्ट्रिंग के विशिष्ट वर्णों की संख्या गिनने का प्रोग्राम

मान लीजिए हमारे पास एक लोअरकेस स्ट्रिंग s है, हमें s के हर सबस्ट्रिंग में विशिष्ट वर्णों की संख्या का योग ज्ञात करना है। यदि उत्तर बहुत बड़ा है तो परिणाम को 10^9+7 से मोड करें।

इसलिए, यदि इनपुट s = "xxy" जैसा है, तो आउटपुट 6 होगा, क्योंकि सबस्ट्रिंग्स और उनकी गिनती हैं:

• "x" : 1

• "x" : 1

• "y" : 1

• "xx" : 0 (क्योंकि "x" विशिष्ट नहीं है)

• "xy" : 2

• "xxy" : 1 (क्योंकि "x" विशिष्ट नहीं है)

हल करने के चरण

• m := 10^9 + 7

• prev_seen := एक नया खाली मैप

• ans := 0

• util() फ़ंक्शन परिभाषित करें। यह i, symbol लेगा

  • prev_seen[symbol] := सिंगल मान -1 वाली सूची

  • prev := prev_seen[symbol]

  • i को prev के अंत में डालें

  • यदि prev का आकार > 2, तो

    • left := prev का पहला तत्व और prev से पहला तत्व हटाएं

    • middle := prev[0], right := prev[1]

    • cnt := (middle - left) * (right - middle)

    • ans := (ans + cnt) mod m

• s में प्रत्येक इंडेक्स i और मान symbol के लिए, util(i, symbol) करें

• prev_seen में प्रत्येक symbol के लिए, util(s का आकार, symbol) करें

• ans लौटाएं

उदाहरण

class Solution:
    def solve(self, s):
        m = 10 ** 9 + 7
        prev_seen = {}
        ans = 0
        def util(i, symbol):
            nonlocal ans
            prev = prev_seen.setdefault(symbol, [-1])
            prev.append(i)
            if len(prev) > 2:
                left = prev.pop(0)
                middle, right = prev
                cnt = (middle - left) * (right - middle)
                ans = (ans + cnt) % m
        for i, symbol in enumerate(s):
            util(i, symbol)
        for symbol in prev_seen:
            util(len(s), symbol)
        return ans

ob = Solution()
s = "xxy"
print(ob.solve(s))

इनपुट

xxy

आउटपुट

6