दिशा स्ट्रिंग को संतुलित करने का कार्यक्रम ताकि प्रत्येक दिशा पायथन में चौथाई बार आए

मान लीजिए कि हमारे पास क्रमशः उत्तर, दक्षिण, पश्चिम और पूर्व के लिए चार दिशाओं "एन", "एस", "डब्ल्यू" और "ई" के साथ एक स्ट्रिंग है। हमें सबसे छोटे सबस्ट्रिंग का आकार खोजना होगा जिसे हम इस तरह अपडेट कर सकते हैं कि चार दिशाओं में से प्रत्येक n/4 बार आए, जहां n स्ट्रिंग s का आकार है।

इसलिए, यदि इनपुट s ="NNSWWESN" जैसा है, तो आउटपुट 1 होगा, यहाँ n 8 है, इसलिए 8/4 2 है, इसलिए यदि हम अंतिम N को E में बदलते हैं, तो सभी दिशाएँ दो बार होंगी।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n :=आकार का
यदि n 0 है, तो
- वापसी 0
तिमाही:=(n / 4) की मंजिल
गिनती :=s में मौजूद प्रत्येक तत्व की आवृत्तियों वाली एक सूची
लक्ष्य :=एक नया नक्शा
गणना में प्रत्येक जोड़ी (dir, cnt) के लिए, करें
- यदि cnt> तिमाही, तो
  - लक्ष्य[dir] :=तिमाही - cnt
यदि लक्ष्य खाली है, तो
- वापसी 0
बाएं:=0
min_len :=inf
प्रत्येक सूचकांक के लिए सही और दिशा dir s में, करते हैं
- अगर डीआईआर निशाने पर है, तो
  - target[dir] :=target[dir] + 1
- लक्ष्य के सभी मूल्यों की न्यूनतम सूची>=0, करते हैं
  - min_len :=न्यूनतम min_len और (दाएं-बाएं + 1)
  - यदि लक्ष्य में [बाएं] है, तो
    - लक्ष्य[s[बाएं]]:=लक्ष्य[s[बाएं]] - 1
    - बाएं:=बाएं + 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"