सबस्ट्रिंग की लंबाई का पता लगाने के लिए प्रोग्राम जहां सबस्ट्रिंग में ज़ीरो की संख्या से दो गुना कम है या पायथन में सबस्ट्रिंग में से तीन गुना के बराबर है

मान लीजिए हमें एक स्ट्रिंग और एक पूर्णांक k दिया गया है। स्ट्रिंग को k बार दोहराया जाता है और दूसरी स्ट्रिंग में बनाया जाता है। हमारा काम नई स्ट्रिंग में सबस्ट्रिंग की लंबाई का पता लगाना है जहां 2 * (सबस्ट्रिंग में शून्य की संख्या) <=3 * (सबस्ट्रिंग में लोगों की संख्या)।

इसलिए, अगर इनपुट k =2, input_str ='0101011' जैसा है, तो आउटपुट 14 होगा।

स्ट्रिंग लंबाई 7 की है। तो, पहली स्ट्रिंग से बनाई गई नई स्ट्रिंग 01010110101011 है। यहां 0s की संख्या 6 है, और 1s की संख्या 8 है। तो, 2 * 6 <=3 * 8. इस प्रकार सबसे बड़ा सबस्ट्रिंग लंबाई 14 की पूरी स्ट्रिंग है।

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

str_len :=input_str का आकार
list_a :=आकार की एक नई सूची (str_len + 1) 0s के साथ आरंभ की गई
list_b :=आकार की एक नई सूची (str_len + 1) 0s के साथ आरंभ की गई
list_b[0] :=एक नया जोड़ा जिसमें (0, 0) हो
0 से str_len की श्रेणी में i के लिए, करें
- list_a[i + 1]:=list_a[i] - 3 *(1 अगर input_str[i] '1' के समान है, और 0) + 2 *(1 अगर input_str[i] '0' के समान है ', और 0)
- list_b[i + 1] :=एक नई जोड़ी (list_a[i + 1], i + 1)
सूची सूची को क्रमित करें_b
temp_list :=आकार की एक नई सूची (str_len + 1) 0s के साथ आरंभ की गई
temp_list[0] :=list_b[0, 1]
0 से str_len की श्रेणी में i के लिए, करें
- temp_list[i + 1] =अधिकतम (temp_list[i], list_b[i + 1, 1])
res :=0
0 से str_len की श्रेणी में i के लिए, करें
- tmp:=list_b[0, 0] - list_a[i]
- अगर list_a[str_len] <=0, तो
  - a :=k - 1
  - अगर tmp + list_a[str_len] * a> 0, तो
    - अगले पुनरावृत्ति के लिए जाएं
- अन्यथा जब tmp> 0, तब
  - अगले पुनरावृत्ति के लिए जाएं
- अन्यथा,
  - a :=न्यूनतम (k - 1, (-tmp / list_a[str_len]) का न्यूनतम मान)
- v :=a * list_a[str_len] - list_a[i]
- b :=(list_b में वह स्थान जहां जोड़े (-v + 1, 0) क्रमबद्ध क्रम को बनाए रखते हुए सम्मिलित किए जा सकते हैं) - 1
- res :=अधिकतम (res, temp_list[b] - i + a * str_len)
रिटर्न रेस

उदाहरण

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

from bisect import bisect_left
def solve(k, input_str):
   str_len = len(input_str)
   list_a = [0] * (str_len + 1)
   list_b = [0] * (str_len + 1)
   list_b[0] = (0, 0)
   for i in range(str_len):
      list_a[i + 1] = list_a[i] - 3 * (input_str[i] == '1') + 2 * (input_str[i] == '0')
      list_b[i + 1] = (list_a[i + 1], i + 1)

   list_b.sort()
   temp_list = [0] * (str_len + 1)
   temp_list[0] = list_b[0][1]
   for i in range(str_len):
      temp_list[i + 1] = max(temp_list[i], list_b[i + 1][1])
   res = 0
   for i in range(str_len):
      tmp = list_b[0][0] - list_a[i]
      if list_a[str_len] <= 0:
         a = k - 1
         if tmp + list_a[str_len] * a > 0:
            continue
      elif tmp > 0:
         continue
      else:
         a = min(k - 1, -tmp // list_a[str_len])

      v = a * list_a[str_len] - list_a[i]
      b = bisect_left(list_b, (-v + 1, 0)) - 1
      res = max(res, temp_list[b] - i + a * str_len)
   return res

print(solve(2, '0101011'))

इनपुट

2, '0101011'