স্ট্রিং s-তে N, S, W, E থাকে। সব দিক ঠিক n/4 বার হয় এমন সবচেয়ে ছোট সাবস্ট্রিং আপডেট করুন।
ইনপুট উদাহরণ
s = "NNSWWESN"আউটপুট: 1 (শেষ N কে E করলে সব দিক ২ বার)
অ্যালগরিদম
- প্রতিটি ডাইরেকশনের ফ্রিকোয়েন্সি কাউন্ট করুন।
- যেসব দিক
quarter-এর চেয়ে বেশি, সেগুলোর এক্সট্রা কাউন্টtarget-এ রাখুন। - স্লাইডিং উইন্ডো দিয়ে সবচেয়ে ছোট উইন্ডো খুঁজুন যেটি কভার করলে বাকি সব দিক ≤
quarterহয়।
পাইথন কোড
from collections import Counter
def solve(s):
n = len(s)
if not n:
return 0
quarter = n // 4
count = Counter(s)
target = {}
for dir, cnt in count.items():
if cnt > quarter:
target[dir] = quarter - cnt # নেগেটিভ ভ্যালু
if not target:
return 0
left, min_len = 0, float("inf")
for right, dir in enumerate(s):
if dir in target:
target[dir] += 1
while min(target.values()) >= 0:
min_len = min(min_len, right - left + 1)
if s[left] in target:
target[s[left]] -= 1
left += 1
return min_len
# টেস্ট
print(solve("NNSWWESN")) # 1ব্যাখ্যা
স্লাইডিং উইন্ডো টেকনিক। target-এ নেগেটিভ ভ্যালু মানে সেই দিকের এক্সট্রা কতটি থাকছে। উইন্ডো ছোট করলে এক্সট্রা কমে।
