復号化した文字列のk番目の文字を求める方法 – Pythonでの実装

問題の概要

エンコードされた文字列では、部分文字列の繰り返しが「部分文字列＋出現回数」の形式で表現されます。たとえば、文字列が pq2rs2 で k=5 の場合、復号化後の文字列は pqpqrsrs となり、5番目の文字は r です。

ここで注意したいのは、出現回数が2桁以上になるケースも存在するという点です。たとえば a12b のような入力では、「a」が12回繰り返されることを正しく読み取れる必要があります。

具体例

入力として string = "pq4r2ts3"、k = 11 が与えられた場合を考えてみましょう。復号化後の文字列は pqpqpqpqrrtststs となるため、11番目の文字である t が出力されます。

解法のアプローチ

この問題は、次の手順で解くことができます。

1. 復号化結果を格納する encoded を空文字列で初期化します。
2. 出現回数 occurrence を 0、走査用のインデックス i を 0 とします。
3. i が文字列の長さに達するまで、以下を繰り返します。
   • temp を空文字列、occurrence を 0 にリセットします。
   • str[i] がアルファベットである間、その文字を temp に追加しながら i を進めます。
   • str[i] が数字である間、occurrence = occurrence * 10 + 数値 として桁を組み立てながら i を進めます。これにより、2桁以上の出現回数にも対応できます。
   • j を 1 から occurrence までループして、encoded に temp を追加します。
   • occurrence が 0 の場合（回数指定がない場合）は、encoded に temp を1回だけ追加します。
4. 最後に encoded[k - 1] を返せば、答えが得られます。

Pythonでの実装例

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

def find_kth_char(input_str, k):
    encoded = ""
    i = 0
    while i < len(input_str):
        temp = ""
        occurrence = 0
        # アルファベット部分を読み取る
        while i < len(input_str) and input_str[i].isalpha():
            temp += input_str[i]
            i += 1
        # 数字部分を読み取る（複数桁にも対応）
        while i < len(input_str) and input_str[i].isdigit():
            occurrence = occurrence * 10 + int(input_str[i])
            i += 1
        # 出現回数に応じて復号化文字列を構築
        if occurrence == 0:
            encoded += temp
        else:
            for _ in range(occurrence):
                encoded += temp
    return encoded[k - 1]

input_str = "pq4r2ts3"
k = 11
print(find_kth_char(input_str, k))

入力

"pq4r2ts3", 11

出力

t

計算量と補足

この手法の時間計算量は、復号化後の文字列の長さを N とすると O(N) です。一方で、出現回数が非常に大きい場合は、復号化後の文字列全体をメモリ上に展開するとメモリを大きく消費する可能性があります。そのようなケースでは、文字列を実際に展開せずに、各ブロックの累積文字数を数えながら k 番目の文字が属する位置を特定する方式が有効です。