Pythonで解く「逆文字列 II」― 2k文字ごとに先頭k文字を反転する方法

問題概要

文字列 s と整数 k が与えられます。文字列の先頭から数えて 2k 文字ごとのブロックについて、それぞれのブロック内の最初の k 文字を反転してください。ただし、以下のルールに従います。

• 残りの文字が 2k 文字未満で k 文字以上の場合： 最初の k 文字のみを反転し、残りは元のままにします。
• 残りの文字が k 文字未満の場合： 残りの文字をすべて反転します。

たとえば、入力が "abcdefgh"、k = 3 のとき、出力は "cbadefhg" となります。これは、最初の 6 文字 "abcdef" のうち先頭 3 文字 "abc" が "cba" に反転され、残りの "gh" は k 文字未満のためすべて反転されて "hg" になるからです。

アルゴリズムの手順

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

• 文字列 s を文字のリスト l に変換します。
• i を k − 1 で初期化します。
• i が「リストの長さ + k」より小さい間、以下を繰り返します。
  • a := l[0 : i−k+1]（すでに処理済みの先頭部分）
  • b := l[i−k+1 : i+1]（今回反転する対象の部分）
  • c := l[i+1 :]（まだ処理していない末尾部分）
  • l := a ＋ b を反転したもの ＋ c として更新します。
  • i に 2k を加算し、次のブロックへ進みます。
• 最後に、リスト l の各文字を連結した文字列を返します。

実装例

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

class Solution:
    def reverseStr(self, s, k):
        l = list(s)
        i = k-1
        while i < len(l)+k:
            a = l[:i-k+1]
            b = l[i-k+1:i+1]
            c = l[i+1:]
            l = a + b[::-1] + c
            i += 2*k
        return ''.join(l)

ob = Solution()
print(ob.reverseStr("abcdefg", 3))

入力

"abcdefg", 3

出力

cbadefg

処理の流れを確認

入力 "abcdefg"、k = 3 の場合、プログラムは次のように動作します。

1. 初期状態：l = ["a","b","c","d","e","f","g"]、i = 2
2. 1 回目のループ：a = ""、b = "abc"、c = "defg"。b を反転すると "cba" になり、l = "cbadefg" となります。その後、i は 8 に更新されます。
3. 2 回目のループ：a = "cbadef"、b = "g"、c = ""。b は 1 文字しかないため反転しても変化せず、結果は "cbadefg" のままです。i が 14 となり条件を満たさなくなるため、ループを終了します。

このように、最終的に "cbadefg" が出力されます。計算量は文字列の長さを n とすると O(n) であり、非常に効率的な解法です。