Pythonでi個のx、j個のy、k個のzからなる部分列の個数を求めるプログラム

文字列 s が「x」「y」「z」で構成されているとします。このとき、「x」が i 個（i ≥ 1）、その後に「y」が j 個（j ≥ 1）、さらにその後に「z」が k 個（k ≥ 1）という順序で並ぶ部分列の総数を求めます。

例えば、入力が s = "xxyz" の場合、出力は 3 になります。これは "xyz" を2通りと "xxyz" を1通りの合計3通り作れるためです。

解き方のアプローチ

この問題は動的計画法（DP）の考え方を使うと効率的に解けます。文字列を先頭から順に走査しながら、次の3つのカウンターを更新していきます。

• x: それまでに見つかった「xのみで構成される部分列」の個数
• y: それまでに見つかった「x…xy…y」という形式の部分列の個数
• z: それまでに見つかった「x…xy…yz…z」という形式の部分列の個数

更新ルール

各文字を読み込んだときの更新式は以下の通りです。

• s[i] が "x" の場合：x = x * 2 + 1（既存のx部分列に新しいxを付け足すか、そこで新しく部分列を始めるかの2択があるため）
• s[i] が "y" の場合：y = y * 2 + x（既存のy部分列を延長するか、これまでのx部分列にyを接続するか）
• s[i] が "z" の場合：z = z * 2 + y（既存のz部分列を延長するか、これまでのy部分列にzを接続するか）

最終的な答えは z の値となります。

Pythonコード例

class Solution:
    def solve(self, s):
        n = len(s)

        x = 0
        y = 0
        z = 0
        for i in range(n):
            if s[i] == "x":
                x *= 2
                x += 1
            if s[i] == "y":
                y *= 2
                y += x
            if s[i] == "z":
                z *= 2
                z += y

        return z

ob = Solution()
print(ob.solve("xxyz"))

入力

"xxyz"

出力

3

計算量について

このアルゴリズムは文字列を一度だけ走査するため、時間計算量は O(n)、追加で必要なメモリは O(1) で済みます。文字列が非常に長い場合でも高速に動作するのが大きな利点です。