मान लीजिए हमारे पास चार दिशाओं "N", "S", "W" और "E" के साथ एक स्ट्रिंग s है जो क्रमशः उत्तर, दक्षिण, पश्चिम और पूर्व के लिए है। हमें सबसे छोटे सबस्ट्रिंग का आकार ढूंढना है जिसे हम अपडेट कर सकते हैं ताकि चार दिशाओं में से प्रत्येक n/4 बार आए, जहां n स्ट्रिंग s का आकार है।
इसलिए, यदि इनपुट है s = "NNSWWESN", तो आउटपुट होगा 1, यहां n 8 है, इसलिए 8/4 2 है, इसलिए यदि हम अंतिम N को E में बदलते हैं, तो सभी दिशाएं दो बार होंगी।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
n := sका आकार- यदि
n0 है, तो:0लौटाएं
quarter := floor(n / 4)count :=sमें मौजूद प्रत्येक तत्व की आवृत्तियों वाली एक सूचीtarget :=एक नया मैपcountमें प्रत्येक जोड़े(dir, cnt)के लिए, करें:- यदि
cnt > quarter, तो:target[dir] := quarter - cnt
- यदि
- यदि
targetखाली है, तो:0लौटाएं
left := 0min_len := infsमें प्रत्येक इंडेक्सrightऔर दिशाdirके लिए, करें:- यदि
dirtargetमें है, तो:target[dir] := target[dir] + 1
- जब
target के सभी मानों की सूची का न्यूनतम >= 0, करें:min_len := min(min_len, right - left + 1)- यदि
s[left]targetमें है, तो:target[s[left]] := target[s[left]] - 1left := left + 1
- यदि
min_lenलौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
from collections import Counter
def solve(s):
n = len(s)
if not n:
return 0
quarter = n // 4
count = Counter(s)
target = dict()
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
s = "NNSWWESN"
print(solve(s))
इनपुट
"NNSWWESN"
आउटपुट
1