Chương trình cân bằng chuỗi hướng để mỗi hướng xảy ra một phần tư lần trong Python

Giả sử chúng ta có một chuỗi s với bốn hướng "N", "S", "W" và "E" cho Bắc, Nam, Tây và Đông tương ứng. Chúng ta phải tìm kích thước của chuỗi con ngắn nhất mà chúng ta có thể cập nhật sao cho mỗi hướng trong bốn hướng xảy ra n / 4 lần mỗi hướng, trong đó n là kích thước của chuỗi s.

Vì vậy, nếu đầu vào giống như s ="NNSWWESN", thì đầu ra sẽ là 1, ở đây n là 8, vậy 8/4 là 2, vì vậy nếu chúng ta thay đổi N cuối cùng thành E, tất cả các hướng sẽ ở đó hai lần.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của s
• nếu n là 0, thì
  • trả về 0
• quý:=tầng của (n / 4)
• count:=danh sách chứa tần số của từng phần tử có trong s
• target:=một bản đồ mới
• đối với mỗi cặp (dir, cnt) được đếm, thực hiện
  • nếu cnt> phần tư, thì
    • target [dir]:=quý - cnt
• nếu mục tiêu trống, thì
  • trả về 0
• trái:=0
• min_len:=inf
• đối với mỗi chỉ mục bên phải và hướng dir in s, thực hiện
  • nếu dir đang ở trong mục tiêu, thì
    • target [dir]:=target [dir] + 1
  • trong khi danh sách tối thiểu của tất cả các giá trị của target> =0, hãy thực hiện
    • min_len:=tối thiểu là min_len và (phải - trái + 1)
    • if s [left] in target, then
      • target [s [left]]:=target [s [left]] - 1
      • left:=left + 1
• trả về min_len

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

"NNSWWESN"

Đầu ra

1