দিক স্ট্রিং ভারসাম্য করার জন্য প্রোগ্রাম যাতে প্রতিটি দিক পাইথনে ত্রৈমাসিক বার ঘটে

ধরুন আমাদের উত্তর, দক্ষিণ, পশ্চিম এবং পূর্বের জন্য যথাক্রমে "N", "S", "W" এবং "E" চারটি দিক সহ একটি স্ট্রিং s আছে। আমাদের এমন সংক্ষিপ্ততম সাবস্ট্রিংটির আকার খুঁজে বের করতে হবে যেটি আমরা আপডেট করতে পারি যাতে চারটি দিক প্রতিটিতে n/4 বার হয়, যেখানে n হল স্ট্রিং s-এর আকার।

সুতরাং, যদি ইনপুটটি s ="NNSWWESN" এর মত হয়, তাহলে আউটপুট হবে 1, এখানে n 8, তাই 8/4 হল 2, তাই যদি আমরা শেষ N থেকে E পরিবর্তন করি, তাহলে সমস্ত দিকনির্দেশ দুইবার থাকবে। পি>

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=s এর আকার
যদি n 0 হয়, তাহলে
- রিটার্ন 0
চতুর্থাংশ :=(n / 4) এর ফ্লোর
গণনা :=s এ উপস্থিত প্রতিটি উপাদানের ফ্রিকোয়েন্সি ধারণকারী একটি তালিকা
লক্ষ্য :=একটি নতুন মানচিত্র
গণনায় প্রতিটি জোড়ার (dir, cnt) জন্য, করুন
- যদি cnt> ত্রৈমাসিক হয়, তাহলে
  - টার্গেট[dir] :=ত্রৈমাসিক - cnt
যদি লক্ষ্য খালি হয়, তাহলে
- রিটার্ন 0
বামে :=0
min_len :=inf
প্রতিটি সূচকের জন্য ডান এবং দিক নির্দেশ s, করুন
- যদি dir টার্গেটে থাকে, তাহলে
  - টার্গেট[ডির] :=টার্গেট[ডির] + 1
- যখন লক্ষ্যের সমস্ত মানের ন্যূনতম তালিকা>=0, কর
  - min_len :=সর্বনিম্ন min_len এবং (ডান - বাম + 1)
  - যদি লক্ষ্যে s[বামে] থাকে, তাহলে
    - টার্গেট[s[বাম]] :=টার্গেট[s[বাম]] - 1
    - বাম :=বাম + 1
মিন_লেন ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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"