Python程式：平衡方向字串，使每個方向出現的次數均為四分之一

假設我們有一個字串s，其中包含四個方向："N"、"S"、"W"和"E"，分別代表北、南、西和東。我們需要找到可以更新的最小子字串的大小，以便這四個方向分別出現n/4次，其中n是字串s的大小。

例如，如果輸入是s = "NNSWWESN"，則輸出為1。這裡n是8，所以8/4是2。如果我們將最後一個N改為E，則所有方向都將出現兩次。

為了解決這個問題，我們將遵循以下步驟：

  • n := s的長度
  • 如果n為0，則
    • 返回0
  • quarter := floor(n / 4)
  • count := 包含s中每個元素頻率的列表
  • target := 一個新的對映
  • 對於count中的每個(dir, cnt)對，執行：
    • 如果cnt > quarter，則
      • target[dir] := quarter - cnt
  • 如果target為空，則
    • 返回0
  • left := 0
  • min_len := inf
  • 對於s中的每個索引right和方向dir，執行：
    • 如果dir在target中，則
      • target[dir] := target[dir] + 1
    • 當target所有值的最小值 >= 0時，執行：
      • min_len := min(min_len, (right - left + 1))
      • 如果s[left]在target中，則
        • target[s[left]] := target[s[left]] - 1
        • left := 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

更新於：2021年10月16日

瀏覽量：384

啟動你的職業生涯

完成課程獲得認證

開始
廣告