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

启动你的职业生涯

完成课程获得认证

开始
广告
© . All rights reserved.