Python में सजातीय सबस्ट्रिंग की संख्या गिनने का प्रोग्राम

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

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

• "x" तीन बार आता है।
• "xx" एक बार आता है।
• "y" दो बार आता है।
• "yy" एक बार आता है।
• "z" तीन बार आता है।
• "zz" दो बार आता है।
• "zzz" एक बार आता है।

समाधान के चरण

1. s := s + "@"
2. h := एक नया मैप
3. prev := s[0]
4. c := 1
5. s में इंडेक्स 1 से अंत तक प्रत्येक 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
6. fin := 0
7. h में प्रत्येक i के लिए:
   • t := len(i)
   • k := 0
   • while t != 0:
     • k := k + t
     • t := t - 1
   • fin := fin + k * h[i]
8. 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"

आउटपुट

13