Pythonで各方向が4分の1回発生するように、方向文字列のバランスをとるプログラム

北、南、西、東にそれぞれ「N」、「S」、「W」、「E」の4つの方向を持つ文字列sがあるとします。 4つの方向のそれぞれがそれぞれn/4回発生するように、更新できる最短のサブストリングのサイズを見つける必要があります。ここで、nはストリングsのサイズです。

したがって、入力がs ="NNSWWESN"の場合、出力は1になり、ここではnは8になり、8/4は2になります。したがって、最後のNをEに変更すると、すべての方向が2回存在します。

これを解決するには、次の手順に従います-

• n：=sのサイズ
• nが0の場合、
  • 0を返す
• クォーター：=（n / 4）のフロア
• count：=sに存在する各要素の頻度を含むリスト
• target：=新しいマップ
• カウントの各ペア（dir、cnt）について、実行します
  • cnt>四半期の場合、
    • target [dir]：=Quarter --cnt
• ターゲットが空の場合、
  • 0を返す
• 左：=0
• min_len：=inf
• sの各インデックスの右方向と方向方向について、次のようにします。
  • dirがターゲットにある場合、
    • target [dir]：=target [dir] + 1
  • ターゲットのすべての値のリストの最小値>=0である間、実行
    • min_len：=min_lenの最小値と（右-左+ 1）
    • ターゲットにs[left]がある場合、
      • target [s [left]]：=target [s [left]]-1
      • 左：=左+ 1
• return 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