ধরুন আমাদের একটি বাইনারি স্ট্রিং s আছে। আমাদের সর্বাধিক একটি "0" থেকে "1" ফ্লিপ করার অনুমতি দেওয়া হয়েছে, আমাদের 1s এর দীর্ঘতম সংলগ্ন সাবস্ট্রিংটির দৈর্ঘ্য খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুটটি s ="1010110001" এর মত হয়, তাহলে আউটপুট হবে 4, যেমন আমরা সূচী 3-এ উপস্থিত শূন্যটিকে ফ্লিপ করি, তাহলে আমরা "1011110001" স্ট্রিং পাব, এখানে 1s-এর দীর্ঘতম সাবস্ট্রিং-এর দৈর্ঘ্য হল 4 .
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=s এর আকার
- উত্তর :=0, ones :=0, বাম :=0, ডান :=0
- যখন ডানে
- যদি s[ডান] "1" এর মত হয়, তাহলে
- ones :=ones + 1
- যখন ডান - বাম + 1 - ones> 1, do
- সরান :=s[বাম]
- যদি রিমুভ করা হয় "1" এর মতো, তাহলে
- ones :=ones - 1
- বাম :=বাম + 1
- উত্তর :=সর্বাধিক উত্তর এবং (ডান - বাম + 1)
- ডান:=ডান + 1
- যদি s[ডান] "1" এর মত হয়, তাহলে
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def solve(s): n = len(s) ans = ones = left = right = 0 while right < n: if s[right] == "1": ones += 1 while right - left + 1 - ones > 1: remove = s[left] if remove == "1": ones -= 1 left += 1 ans = max(ans, right - left + 1) right += 1 return ans s = "1010110001" print(solve(s))
ইনপুট
"1010110001"
আউটপুট
4
