用 Python 编写程序平衡方向字符串，使每个方向出现四分之一次

pythonserver side programmingprogramming更新于 2026/1/11 7:08:17

假设我们有一个字符串 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 of (n / 4)
count := 包含 s 中存在的每个元素的频率的列表
target := 一个新的map
对于 count 中的每个对 (dir, cnt)，执行
- 如果 cnt >季度，则
  - target[dir] := quarter - cnt
如果 target 为空，则
- 返回 0
left := 0
min_len := inf
对于 s 中的每个右索引和方向 dir，执行
- 如果 dir 在 target 中，则
  - target[dir] := target[dir] + 1
- 当 target 所有值列表中的最小值 >= 0 时，执行
  - min_len := 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))