पायथन में एक स्ट्रिंग के हर विकल्प के अलग-अलग वर्णों की संख्या की गणना करने का कार्यक्रम

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

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

• "एक्स" :1

• "एक्स" :1

• "वाई" :1

• "xx" :0 (जैसा कि "x" अलग नहीं है)

• "xy" :2

• "xxy" :1 ("जैसा कि "x" अलग नहीं है)

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

• मी :=10^9 + 7

• prev_seen :=एक नया खाली नक्शा

• उत्तर :=0

• उपयोग() फ़ंक्शन को परिभाषित करें। यह मैं, प्रतीक लेगा

• prev_seen[symbol] :=एकल मान वाली एक सूची −1

• पिछला:=prev_seen[प्रतीक]

• पिछले के अंत में i डालें

• अगर पिछला का आकार> 2, तो

  • बायां:=पिछला का पहला तत्व और पिछला से पहला तत्व हटाएं

  • मध्य:=पिछला[0], दाएं:=पिछला[1]

  • cnt :=(मध्य - बाएँ) *(दाएँ - मध्य)

  • उत्तर:=(Ans + cnt) मॉड एम

• प्रत्येक अनुक्रमणिका i और s में मान चिह्न के लिए, करें

  • उपयोग (i, प्रतीक)

• prev_seen में प्रत्येक प्रतीक के लिए, करें

  • उपयोग (एस का आकार, प्रतीक)

• वापसी उत्तर

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

उदाहरण

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