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

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

ইনপুট k = 2, input_str = '0101011' হলে আউটপুট হবে 14।

স্ট্রিংয়ের দৈর্ঘ্য ৭। নতুন স্ট্রিং: 01010110101011। এখানে শূন্যের সংখ্যা ৬, একের সংখ্যা ৮। সুতরাং, 2×6 ≤ 3×8। সর্বোচ্চ সাবস্ট্রিং হল পুরো স্ট্রিং যার দৈর্ঘ্য ১৪।

সমাধানের ধাপসমূহ

str_len := input_str-এর দৈর্ঘ্য
list_a := (str_len + 1) আকারের ০ দিয়ে ইনিশিয়ালাইজড লিস্ট
list_b := (str_len + 1) আকারের ০ দিয়ে ইনিশিয়ালাইজড লিস্ট
list_b[0] := (0, 0) জোড়া
i = 0 থেকে 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 সর্ট করুন
temp_list := (str_len + 1) আকারের ০ দিয়ে ইনিশিয়ালাইজড লিস্ট
temp_list[0] := list_b[0][1]
i = 0 থেকে str_len পর্যন্ত:
- temp_list[i+1] = max(temp_list[i], list_b[i+1][1])
res := 0
i = 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 হয়, তবে পরবর্তী iteration-এ যান
- অন্যথায় যদি tmp > 0 হয়, তবে পরবর্তী iteration-এ যান
- অন্যথায়:
  - a := min(k - 1, floor(-tmp / list_a[str_len]))
- v := a × list_a[str_len] - list_a[i]
- b := (list_b-এ (-v + 1, 0) জোড়া ইনসার্ট করার পজিশন) - 1
- res := max(res, temp_list[b] - i + a × str_len)
res ফেরত দিন

উদাহরণ

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'