【Python】方向文字列のバランスを取る：各方向がn/4回ずつ出現するようにする最短置換区間の求め方

文字列 s には、「N」（北）、「S」（南）、「W」（西）、「E」（東）の4種類の方向文字が含まれているとします。文字列の長さを n としたとき、4つの方向がそれぞれちょうど n/4 回ずつ出現するように書き換えられる、最短の部分文字列（連続区間）の長さを求めるのがこの問題です。

例として、入力が s = "NNSWWESN" の場合を考えてみましょう。n = 8 なので n/4 = 2 です。末尾の「N」を「E」に1文字だけ書き換えれば、すべての方向が2回ずつ出現するバランスの取れた文字列になります。したがって、出力は 1 です。

アルゴリズムの考え方

この問題はスライディングウィンドウ（尺取り法）を使うと効率的に解けます。ポイントは、ウィンドウの外側の文字はそのまま残るため、置き換える区間には「出現数が n/4 を超えている方向」について超過分（現在のカウント − n/4）以上の文字が含まれていなければならない、という点です。条件を満たす最小のウィンドウを、左右のポインタで絞り込んでいきます。

手順

• n に文字列 s の長さを代入します。
• n が 0 の場合は 0 を返します。
• quarter に n / 4 の切り捨て値を設定します。
• count に、s に含まれる各文字の出現頻度を格納します。
• target として新しいマップを作成します。
• count の各ペア (dir, cnt) について、cnt > quarter であれば target[dir] = quarter − cnt とします（負の値＝不足分を記録）。
• target が空の場合は、すでにバランスが取れているため 0 を返します。
• left = 0、min_len = 無限大 で初期化します。
• s の各インデックス right とその文字 dir に対して、以下を繰り返します。
  • dir が target に存在すれば、target[dir] を +1 します。
  • target の全値の最小値が 0 以上である間、次を繰り返します。
    • min_len を min_len と (right − left + 1) の小さい方で更新します。
    • s[left] が target に存在すれば target[s[left]] を −1 し、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