पायथन में एक स्ट्रिंग को विभाजित करने के तरीकों की संख्या खोजने के लिए कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी स्ट्रिंग है, हम 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" की तरह विभाजित कर सकते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

गिनती :=s में 1s की संख्या गिनें
म :=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 का भागफल या कम_e <=काउंट/3 का भागफल, करें
- यदि s[बाएं] "1" के समान है, तो
  - cum_s :=cum_s + 1
- यदि s[दाएं] "1" के समान है, तो
  - cum_e :=cum_e + 1
- यदि cum_s, गिनती/3 के भागफल के समान है, तो
  - Ans[0] :=ans[0] + 1
- यदि cum_e, गिनती/3 के भागफल के समान है, तो
  - उत्तर[1] :=उत्तर[1] + 1
- बाएं:=बाएं + 1
- दाएं:=दाएं - 1
वापसी (उत्तर [0] * उत्तर [1]) मॉड एम

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

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"