Pythonでk種類の一意な文字を含む最長部分文字列を求める方法【スライディングウィンドウ法】

問題の概要

文字列が与えられたとき、ちょうどk個の一意な（重複しない）文字を含む最長の部分文字列を返すことを考えます。条件を満たす最長の部分文字列が複数存在する場合は、そのうちのどれか1つを返せば問題ありません。

例えば、入力が s = "ppqprqtqtqt"、k = 3 の場合、出力は長さ7の「rqtqtqt」となります。

解法の考え方：スライディングウィンドウ法

この問題はスライディングウィンドウ（尺取り法）と呼ばれる手法で効率的に解けます。ウィンドウの右端を1文字ずつ伸ばしていき、一意な文字の種類数が制約を超えたら左端を縮める、という操作を繰り返すことで答えを求めます。

アルゴリズムの手順

1. N := 26 とする（英小文字26種類に対応）
2. 補助関数 is_ok(count, k) を定義する
   • val := 0 で初期化する
   • i を 0 から N-1 までループし、count[i] > 0 なら val を 1 増やす（現在使われている文字の種類数を数える）
   • k >= val が成立すれば true を返す
3. メイン処理では以下を実行する
   • unique := 0、size := 文字列 s の長さとする
   • サイズ N の配列 count を 0 で初期化する
   • i を 0 から size-1 までループし、各文字の出現回数をカウントする。初めて現れた文字であれば unique を 1 増やす
   • unique < k の場合、条件を満たす部分文字列が存在しないため、そこで処理を終了する
   • start := 0、end := 0、window_length := 1、window_start := 0 で初期化する
   • count を再び 0 で初期化し、s[0] のカウントを 1 にする
   • i を 1 から size-1 までループする
     • s[i] のカウントを 1 増やし、end を 1 増やす（ウィンドウを右へ拡張）
     • is_ok(count, k) が false の間、s[start] のカウントを 1 減らして start を 1 増やす（ウィンドウを左側から縮小）
     • end - start + 1 > window_length であれば、window_length と window_start を更新する
4. window_start から window_start + window_length までの部分文字列を返す

Pythonでの実装例

それでは、実際のコードを見てみましょう。

N = 26

def is_ok(count, k):
    val = 0
    for i in range(N):
        if count[i] > 0:
            val += 1
    return (k >= val)

def k_unique_chars(s, k):
    unique = 0
    size = len(s)
    count = [0] * N
    for i in range(size):
        if count[ord(s[i]) - ord('a')] == 0:
            unique += 1
        count[ord(s[i]) - ord('a')] += 1
    if unique < k:
        return "Not sufficient characters"
    start = 0
    end = 0
    window_length = 1
    window_start = 0
    count = [0] * len(count)
    count[ord(s[0]) - ord('a')] += 1
    for i in range(1, size):
        count[ord(s[i]) - ord('a')] += 1
        end += 1
        while not is_ok(count, k):
            count[ord(s[start]) - ord('a')] -= 1
            start += 1
        if end - start + 1 > window_length:
            window_length = end - start + 1
            window_start = start
    return s[window_start:window_start + window_length]

s = "ppqprqtqtqt"
k = 3
print(k_unique_chars(s, k))

実行結果

入力

"ppqprqtqtqt", 3

出力

rqtqtqt

計算量のポイント

この実装では、各文字に対してウィンドウへの追加と除去がそれぞれ高々1回ずつしか行われないため、時間計算量は O(n) となります。また、使用しているのは固定サイズ26の配列だけなので、空間計算量も O(1) です。すべての部分文字列を総当たりで調べる O(n²) の素朴なアプローチと比べて大幅に効率化できる点が、この手法の大きな魅力です。