Pythonで文字列を単調な部分文字列に分割する最小数を求める方法

問題概要

小文字のみで構成された文字列 s が与えられます。この文字列を、各部分文字列が「非減少」または「非増加」のいずれかを満たすように分割するとき、必要な連続部分文字列の最小個数を求めます。

例えば、「pqqqr」は非減少文字列、「qqqp」は非増加文字列です。

入出力の例

入力が s = "pqrsrqp" の場合、出力は 2 になります。「pqrs」（非減少）と「rqp」（非増加）という2つの部分文字列に分割できるためです。

解法のアプローチ

この問題は、文字列を左から右へ走査しながら、昇順と降順の方向が切り替わる箇所を検出することで解けます。具体的には、以下の手順に従います。

• s が空文字列の場合は 0 を返します。
• 変数 last に先頭の文字、direction に 1（未確定）、count に 1 を初期値として設定します。
• s の各文字について、以下の処理を繰り返します。
  • 現在の文字が前の文字より大きい場合（昇順の変化）：
    • direction が 1（未確定）なら、direction を 0（非減少モード）に更新します。
    • direction が 2（非増加モード）なら、ここで分割が必要になるため count を 1 増やし、direction を 1 にリセットします。
  • 現在の文字が前の文字より小さい場合（降順の変化）：
    • direction が 1（未確定）なら、direction を 2（非増加モード）に更新します。
    • direction が 0（非減少モード）なら、ここで分割が必要になるため count を 1 増やし、direction を 1 にリセットします。
• 最後に count を返します。

Python実装例

理解を深めるために、以下の実装例を見てみましょう。

def solve(s):
    if not s:
        return 0

    last = s[0]
    direction = 1
    count = 1

    for char in s:
        if char > last:
            if direction == 1:
                direction = 0
            elif direction == 2:
                direction = 1
                count += 1
        elif char < last:
            if direction == 1:
                direction = 2
            elif direction == 0:
                direction = 1
                count += 1
        last = char

    return count

s = "pqrsrqp"
print(solve(s))

入力

"pqrsrqp"

出力

2

アルゴリズムのポイント

direction 変数は、現在の単調性の状態を表しています。1 はまだ方向が未確定であること、0 は非減少（昇順）、2 は非増加（降順）を意味します。走査中に現在の方向と逆の変化が検出された時点で新しいグループを開始し、カウントを増やしながら方向をリセットしていきます。

このアルゴリズムの時間計算量は O(n)（n は文字列の長さ）、空間計算量は O(1) であり、非常に効率的です。等しい文字が連続する場合は方向の変化とみなされないため、どちらの単調性にも属させることができます。