পাইথনে একটি স্ট্রিং বিভক্ত করার উপায় খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি স্ট্রিং s আছে আমরা s কে 3টি অ-খালি স্ট্রিং s1, s2, s3 এ বিভক্ত করতে পারি যাতে (s1 concatenate s2 concatenate s3 =s)। আমাদের খুঁজে বের করতে হবে কতগুলো উপায়ে s কে বিভক্ত করা যায় যাতে s1, s2 এবং s3 তে '1' অক্ষরের সংখ্যা সমান হয়। উত্তরটি অনেক বড় হতে পারে তাই উত্তর মোড 10^9+7 ফেরত দিন।

সুতরাং, যদি ইনপুট s ="11101011" এর মতো হয়, তাহলে আউটপুট হবে 2 কারণ আমরা সেগুলিকে "11 | 1010 | 11" এবং "11 | 101 | 011" এর মতো বিভক্ত করতে পারি।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:

গণনা :=গণনা সংখ্যা 1 সেকেন্ডে
m :=10^9 + 7
উত্তর :=আকার 2 এর একটি অ্যারে এবং 0 দিয়ে পূরণ করুন
যদি গণনা মোড 3 0 এর মত না হয়, তাহলে
- রিটার্ন 0
অন্যথায় যখন গণনা 0 এর সমান হয়, তখন
- রিটার্ন (nCr যেখানে n এর সাইজ s -1 এবং r 2) mod m
বামে :=0
ডান:=s - 1 এর আকার
cum_s :=0, cum_e :=0
যখন cum_s <=গণনার ভাগফল/3 বা cum_e <=গণনার ভাগফল/3, কর
- যদি s[left] "1" এর মত হয়, তাহলে
  - cum_s :=cum_s + 1
- যদি s[ডান] "1" এর মত হয়, তাহলে
  - cum_e :=cum_e + 1
- যদি cum_s গণনা/3 এর ভাগফলের সমান হয়, তাহলে
  - উত্তর[0] :=ans[0] + 1
- যদি cum_e গণনা/3 এর ভাগফলের সমান হয়, তাহলে
  - উত্তর[1] :=ans[1] + 1
- বাম :=বাম + 1
- ডান :=ডান - 1
রিটার্ন (ans[0]*ans[1]) mod m

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

উদাহরণ

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
   while(cum_s <= count//3 or cum_e <= count//3):
      if s[left] == "1":
         cum_s+=1
      if s[right] == "1":
         cum_e+=1
      if cum_s == count//3:
         ans[0]+=1
      if cum_e == count//3:
         ans[1]+=1
      left += 1
      right -= 1
   return (ans[0]*ans[1]) % m
s = "11101011"
print(solve(s))

ইনপুট

"11101011"