সাবস্ট্রিং এর দৈর্ঘ্য বের করার প্রোগ্রাম যেখানে সাবস্ট্রিং-এ শূন্যের সংখ্যা দুইগুণ, পাইথনের সাবস্ট্রিং-এর সংখ্যার চেয়ে তিনগুণ কম বা সমান

ধরুন আমাদের একটি স্ট্রিং এবং একটি পূর্ণসংখ্যা k দেওয়া হয়েছে। স্ট্রিংটি k বার পুনরাবৃত্তি হয় এবং অন্য একটি স্ট্রিং তৈরি করা হয়। আমাদের কাজ হল নতুন স্ট্রিং-এ সাবস্ট্রিং-এর দৈর্ঘ্য খুঁজে বের করা যেখানে 2 * (সাবস্ট্রিংয়ে শূন্যের সংখ্যা) <=3 * (সাবস্ট্রিং-এর সংখ্যা)।

সুতরাং, যদি ইনপুট হয় k =2, input_str ='0101011', তাহলে আউটপুট হবে 14।

স্ট্রিংটির দৈর্ঘ্য 7। সুতরাং, প্রথম স্ট্রিং থেকে যে নতুন স্ট্রিংটি তৈরি করা হয়েছে তা হল 0101011010101011। এখানে 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 রেঞ্জের জন্য, কর
- 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 রেঞ্জের জন্য, কর
- temp_list[i + 1] =সর্বাধিক (temp_list[i], list_b[i + 1, 1])
res :=0
আমি 0 থেকে str_len রেঞ্জের জন্য, কর
- 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 :=(লিস্ট_বি-তে অবস্থান যেখানে সাজানো ক্রম বজায় রেখে জোড়া (-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'