পাইথনে বাইনারি স্ট্রিং তিনটি সমান '১' সম্বলিত অংশে ভাগ করার পদ্ধতির সংখ্যা

একটি বাইনারি স্ট্রিং s তিনটি নন-এম্পটি স্ট্রিং s1, s2, s3-এ ভাগ করতে হবে যাতে s1 + s2 + s3 = s এবং তিনটিতে '১' এর সংখ্যা সমান হয়। উত্তর বড় হতে পারে, তাই 10⁹+7 দিয়ে মডুলো নিতে হবে।

উদাহরণ:

ইনপুট: s = "11101011"

আউটপুট: 2 কারণ ভাগ করা যায়: "11 | 1010 | 11" এবং "11 | 101 | 011"।

সমাধানের পদ্ধতি:

1. count = s.count("1") - মোট '১' গণনা করুন
2. m = 10**9 + 7
3. যদি count % 3 != 0: রিটার্ন 0
4. যদি count == 0: রিটার্ন comb(len(s)-1, 2) % m (সব শূন্য হলে যেকোনো দুই জায়গায় কাটা যায়)
5. প্রতি অংশে target = count // 3টি '১' থাকবে
6. বাম থেকে left এবং ডান থেকে right পয়েন্টার দিয়ে ক্যাটে target সংখ্যক '১' পাওয়া পর্যন্ত যান
7. ans[0] = বাম পক্ষের বৈধ কাটার সংখ্যা, ans[1] = ডান পক্ষের বৈধ কাটার সংখ্যা
8. রিটার্ন (ans[0] * ans[1]) % m

পাইথন কোড:

from math import comb

def solve(s):
    count = s.count("1")
    m = 10**9 + 7
    ans = [0, 0]
    if count % 3 != 0:
        return 0
    elif count == 0:
        return comb(len(s)-1, 2) % m
    
    left = 0
    right = len(s) - 1
    cum_s = 0
    cum_e = 0
    target = count // 3
    
    while cum_s <= target or cum_e <= target:
        if s[left] == "1":
            cum_s += 1
        if s[right] == "1":
            cum_e += 1
        if cum_s == target:
            ans[0] += 1
        if cum_e == target:
            ans[1] += 1
        left += 1
        right -= 1
    
    return (ans[0] * ans[1]) % m

s = "11101011"
print(solve(s))  # আউটপুট: 2

টেস্ট কেস:

ইনপুট: "11101011"

আউটপুট: 2