একটি বাইনারি স্ট্রিং s দেওয়া আছে। সর্বোচ্চ একটি "0" কে "1" এ ফ্লিপ করতে পারবেন। ফ্লিপ করার পর 1-এর সবচেয়ে লম্বা কন্টিগুয়াস সাবস্ট্রিংর দৈর্ঘ্য বের করতে হবে।
উদাহরণ: s = "1010110001" হলে আউটপুট 4। ইনডেক্স ৩-এর 0 ফ্লিপ করলে "1011110001" হয়, যেখানে 1111 দৈর্ঘ্য ৪।
সমাধানের পদ্ধতি
স্লাইডিং উইন্ডো (টু পয়েন্টার) টেকনিক। উইন্ডোতে সর্বোচ্চ একটি 0 থাকবে।
left, right= উইন্ডোর দুটি পয়েন্টার।ones= উইন্ডোতে1-এর সংখ্যা।rightবাড়িয়ে উইন্ডো বড় করুন।- যদি উইন্ডোতে একের চেয়ে বেশি
0হয় (right - left + 1 - ones > 1), তবেleftবাড়িয়ে উইন্ডো ছোট করুন। - প্রতিটি ধাপে সর্বোচ্চ উইন্ডো সাইজ আপডেট করুন।
পাইথন কোড
def solve(s):
n = len(s)
ans = ones = left = right = 0
while right < n:
if s[right] == "1":
ones += 1
# উইন্ডোতে ০-এর সংখ্যা > 1 হলে left বাড়ান
while right - left + 1 - ones > 1:
if s[left] == "1":
ones -= 1
left += 1
ans = max(ans, right - left + 1)
right += 1
return ans
# টেস্ট
s = "1010110001"
print(solve(s)) # আউটপুট: 4সময় জটিলতা
O(n) - প্রতিটি ক্যারেক্টার hoogstens একবার প্রক্রিয়া হয়। স্পেস O(1)।
