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

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

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

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

समाधान दृष्टिकोण

प्रीफिक्स सम सरणी का उपयोग करके संतुलन ट्रैक करें
सॉर्टेड प्रीफिक्स सम और उनकी स्थितियों को बनाए रखें
दोहराई गई स्ट्रिंग के लिए स्लाइडिंग विंडो दृष्टिकोण का उपयोग करें
बाइनरी खोज के साथ वैध सबस्ट्रिंग ढूंढें

उदाहरण कार्यान्वयन

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'