পাইথনে স্ট্রিংয়ের সব সাবস্ট্রিংয়ের স্বতন্ত্র ক্যারেক্টার সংখ্যায়ের যোগফল

একটি লোয়ারকেস স্ট্রিং s দেওয়া আছে। s-এর সব সাবস্ট্রিং-এ যেসব ক্যারেক্টার একবারই আছে (Distinct) তাদের সংখ্যা যোগ করে মডুলো 10^9+7 দিয়ে রিটার্ন করতে হবে।

উদাহরণ: s = "xxy" → সাবস্ট্রিং ও কাউন্ট: "x":1, "x":1, "y":1, "xx":0, "xy":2, "xxy":1 → মোট 6।

সমাধানের ধাপসমূহ (কন্ট্রিবিউশন টেকনিক)

1. m := 10^9 + 7, prev_seen := ডিকশনারি (ক্যারেক্টার -> লাস্ট পজিশন লিস্ট), ans := 0।

2. util(i, symbol) ফাংশন:

   • prev_seen[symbol]-এ i অ্যাপেন্ড করুন।

   • যদি লিস্টের সাইজ > ২ হয়, তবে বাম থেকে ৩টি পজিশন left, middle, right নিয়ে cnt = (middle-left)*(right-middle) কালকুলেট করুন।

   • ans = (ans + cnt) % m আপডেট করুন।

3. প্রতিটি (i, symbol) ∈ s এর জন্য util(i, symbol) কল করুন।

4. শেষে প্রতিটি সিম্বলের জন্য util(len(s), symbol) কল করে বাকি কন্ট্রিবিউশন যোগ করুন।

5. 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