একটি লোয়ারকেস স্ট্রিং s দেওয়া আছে যাতে ইংরেজি অক্ষর এবং "?" সিম্বল থাকে। প্রতিটি "?" কে যেকোনো লোয়ারকেস লেটার দিয়ে রিপ্লেস করতে পারবেন অথবা সরিয়ে দিতে পারবেন। 'a' দিয়ে শুরু হওয়া সবচেয়ে লম্বা কনsekutিভ ইনক্রিজিং সাবস্ট্রিং (যেমন abcde...) এর দৈর্ঘ্য বের করতে হবে।
উদাহরণ: s = "vta???defke" হলে আউটপুট 6। কারণ "?" গুলোকে "bcd" দিয়ে রিপ্লেস করলে "vtabcdefke" হয় এবং "abcdef" (দৈর্ঘ্য ৬) সবচেয়ে লম্বা।
সমাধানের পদ্ধতি
একটি পাসে স্ট্রিং স্ক্যান করুন এবং তিনটি ভেরিয়েবল রক্ষা করুন:
length: বর্তমান কনsekutিভ সিকোয়েন্সের দৈর্ঘ্য (যেখানে'a'= ১,'b'= ২, ...)qmarks: বর্তমানে প্রাপ্ত"?"এর সংখ্যা।maxlen: সর্বোচ্চ দৈর্ঘ্য পাওয়া গেছে।
প্রতিটি ক্যারেক্টার c এর জন্য:
c == "?"হলেqmarks++।- অন্যथा
idx = ord(c) - ord('a')। যদিidxবর্তমান সিকোয়েন্সে ফিট হয় (আগের অক্ষরের পরের অক্ষর বাqmarksদিয়ে পূরণযোগ্য) তবেlength = idx + 1, অন্যথায়length = 0।qmarks = 0রিসেট করুন। maxlen = max(maxlen, min(length + qmarks, 26))আপডেট করুন (২৬ এর বেশি হয় না কারণ অ্যালফাবেট ২৬টি)।
পাইথন কোড
def solve(s):
maxlen = length = qmarks = 0
for c in s:
if c == "?":
qmarks += 1
else:
idx = ord(c) - ord("a")
# idx বর্তমান সিকোয়েন্সের পরবর্তী অক্ষর হলে বা qmarks দিয়ে পূরণযোগ্য হলে
length = idx + 1 if length <= idx <= length + qmarks or idx <= qmarks else 0
qmarks = 0
maxlen = max(maxlen, min(length + qmarks, 26))
return maxlen
# টেস্ট
s = "vta???defke"
print(solve(s)) # আউটপুট: 6সময় জটিলতা
O(n) - একক পাস। স্পেস O(1)।
