ধরুন আমাদের একটি বাইনারি স্ট্রিং s আছে। যদি আমরা স্ট্রিংটিতে সর্বাধিক একজোড়া অক্ষর অদলবদল করতে পারি, তাহলে আমাদের 1s-এর দীর্ঘতম সংলগ্ন সাবস্ট্রিং-এর ফলস্বরূপ দৈর্ঘ্য খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুটটি s ="1111011111" এর মত হয়, তাহলে আউটপুট হবে 9, কারণ আমরা s[4] এবং s[9] অদলবদল করে 9টি পরপর 1s পেতে পারি।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- l :=0, cnt :=0, উত্তর :=0
- র জন্য 0 থেকে s আকারের পরিসরে, করুন
- cnt :=cnt + (1 যখন s[r] একই হয় "0" অন্যথায় 0)
- যদি cnt> 1, তারপর
- cnt :=cnt - (1 যখন s[l] একই হয় "0" অন্যথায় 0)
- l :=l + 1
- উত্তর :=সর্বাধিক উত্তর এবং (r - l + 1)
- সর্বনিম্ন উত্তর প্রদান করুন এবং 1 এর মধ্যে s
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution:
def solve(self, s):
l = 0
cnt = 0
ans = 0
for r in range(len(s)):
cnt += s[r] == "0"
if cnt > 1:
cnt -= s[l] == "0"
l += 1
ans = max(ans, r - l + 1)
return min(ans, s.count("1"))
ob = Solution()
s = "1111011111"
print(ob.solve(s)) ইনপুট
"1111011111"
আউটপুট
9
