পাইথনে একটি স্ট্রিংয়ের প্রতিটি সাবস্ট্রিংয়ের স্বতন্ত্র অক্ষরের সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের একটি ছোট হাতের স্ট্রিং 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 :=একটি নতুন খালি মানচিত্র

• উত্তর :=0

• একটি ফাংশন util() সংজ্ঞায়িত করুন। এটি i, প্রতীক

  নেবে

• prev_seen[symbol] :=একক মান −1

  সহ একটি তালিকা

• পূর্ববর্তী :=পূর্বের_দেখা [প্রতীক]

• পূর্বের শেষে i সন্নিবেশ করান

• যদি পূর্ববর্তী> 2 এর আকার, তাহলে

  • বাম :=পূর্বের প্রথম উপাদান এবং পূর্ববর্তী থেকে প্রথম উপাদান মুছে ফেলুন

  • মধ্যম :=পূর্ববর্তী[0], ডানে :=পূর্ববর্তী[1]

  • cnt :=(মধ্য - বাম) *(ডান - মধ্যম)

  • উত্তর :=(ans + cnt) mod m

• প্রতিটি সূচক i এবং s-এ মান চিহ্নের জন্য, do

  • util(i, প্রতীক)

• prev_seen-এ প্রতিটি প্রতীকের জন্য করুন

  • util(s এর আকার , প্রতীক)

• উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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