পাইথনে হোমোজিনাস সাবস্ট্রিংয়ের সংখ্যা গণনার প্রোগ্রাম

মান লিজিয়ে আমাদের একটি স্ট্রিং আছে s, আমাদের s-এর হোমোজিনাস সাবস্ট্রিংয়ের সংখ্যা বের করতে হবে। উত্তর খুব বড় হতে পারে, তাই 10^9+7 দিয়ে মডুলো রিটার্ন করতে হবে। একটি স্ট্রিং হোমোজিনাস বলা হয় যখন স্ট্রিংটির সকল ক্যারেক্টার একই থাকে।

যেমন, ইনপুট হলে s = "xyyzzzxx", তবে আউটপুট হবে 13 কারণ হোমোজিনাস সাবস্ট্রিংগুলো নিচের মতো:

"x" ৩ বার আসে।
"xx" ১ বার আসে।
"y" ২ বার আসে।
"yy" ১ বার আসে।
"z" ৩ বার আসে।
"zz" ২ বার আসে।
"zzz" ১ বার আসে।

তাই, (3 + 1 + 2 + 1 + 3 + 2 + 1) = 13।

সমাধানের ধাপসমূহ

s := s + "@"
h := নতুন ম্যাপ
prev := s[0]
c := 1
s-এর ইন্ডেক্স ১ থেকে শেষ পর্যন্ত প্রতিটি i এর জন্য:
- যদি prev != i হয়, তবে:
  - যদি prev*c h-এ থাকে, তবে h[prev*c] := h[prev*c] + 1
  - অন্যথায়, h[prev*c] := 1
  - c := 1
- যদি prev == i হয়, তবে c := c + 1
- prev := i
fin := 0
h-এ প্রতিটি i এর জন্য:
- t := len(i)
- k := 0
- t != 0 থাকা পর্যন্ত:
  - k := k + t
  - t := t - 1
- fin := fin + k * h[i]
fin % 1000000007 রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

def solve(s):
    s += "@"
    h = {}
    prev = s[0]
    c = 1
    for i in s[1:]:
        if prev != i:
            if prev * c in h:
                h[prev * c] += 1
            else:
                h[prev * c] = 1
            c = 1
        if prev == i:
            c += 1
        prev = i
    fin = 0
    for i in h:
        t = len(i)
        k = 0
        while t != 0:
            k += t
            t -= 1
        fin += k * h[i]
    return fin % 1000000007

s = "xyyzzzxx"
print(solve(s))

ইনপুট

"xyyzzzxx"