在Python中使每个方向出现四分之一次的平衡方向字符串的程序

假设我们有一个由四个方向“N”、“S”、“W”和“E”组成的字符串s，分别表示北、南、西和东。我们必须找到我们可以更新的最短子字符串大小，使得每个方向都出现n/4次，其中n是字符串s的大小。

因此，如果输入是s =“NNSWWESN”，则输出将为1，这里n为8，因此如果我们将最后一个N更改为E，所有方向将出现两次。

为了解决这个问题，我们将按照以下步骤进行−

n：= s的大小
如果n为0，则
- 返回0
quarter：=（n/4）向下取整
count：= 包含s中每个元素频率的列表
target：=一个新的映射
对于count中的每对（dir，cnt），执行以下操作
- 如果cnt>quarter，则
  - target [dir]：= quarter-cnt
如果目标为空，则
- 返回0
left：=0
min_len：= inf
对于s中的每个索引右和方向dir，执行以下操作
- 如果dir在target中，则
  - target [dir]：= target [dir]+ 1
- 当目标的所有值的列表的最小值≥0时，执行以下操作
  - min_len：= min（min_len和（右-左+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))