C++で文字列の各文字をシフトするアルゴリズムを実装する方法

小文字のみで構成された文字列 S と整数型配列 shifts が与えられたとします。ここで「シフト」とは、ある文字をアルファベット順で次の文字に置き換えることを意味し、z の場合は a に戻ります（循環）。そして、各 shifts[i] = x に対して、文字列 S の先頭から i+1 文字目までをそれぞれ x 回シフトします。すべてのシフト操作を適用した後の最終的な文字列を求めるのがこの問題です。

例として、文字列が "abc"、shifts = [3, 5, 9] の場合を考えてみましょう。

• 最初の1文字を3回シフト → "dbc"
• 最初の2文字をそれぞれ5回シフト → "igc"
• 最初の3文字をそれぞれ9回シフト → "rpl"（これが答え）

解法のアプローチ

この問題を素朴に解くと、各シフト操作ごとに文字を一つずつ動かす必要があり、計算量が大きくなってしまいます。そこで有効なのが「後ろからの累積和」の考え方です。ある位置の文字は、それ以降のすべてのシフト操作の影響を受けるため、配列を後ろから走査しながらシフト量を累積していきます。

具体的には以下の手順で解きます。

• i をシフト配列のサイズ − 2 から 0 まで降順にループする
  • shifts[i] += shifts[i + 1]（後続のシフト量を累積）
  • shifts[i] %= 26（オーバーフロー防止のため26で剰余を取る）
• i を 0 から文字列 S のサイズ − 1 までループする
  • S[i] = ((S[i] - 'a') + shifts[i]) % 26 + 'a'（実際に文字をシフト）
• S を返す

この方法により、時間計算量 O(n)、空間計算量 O(1)（入力配列を再利用する場合）で効率的に解くことができます。

C++での実装例

以下に実際のC++コードを示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string shiftingLetters(string S, vector<int>& shifts) {
        // 後ろから累積シフト量を計算
        for(int i = shifts.size() - 2 ;i >=0; i--){
            shifts[i] += shifts[i + 1];
            shifts[i] %= 26;
        }
        // 各文字を対応するシフト量だけ移動
        for(int i = 0; i < S.size(); i++) {
            S[i] = ( ((S[i] - 'a') + shifts[i]) % 26 + 'a');
        }
        return S;
    }
};
main(){
    vector<int> v = {3,5,9};
    Solution ob;
    cout << (ob.shiftingLetters("abc", v));
}

入力

"abc"
[3,5,9]

出力

rpl

まとめ

この問題のポイントは、各文字が受けるシフト量を後ろから累積して求める点にあります。これにより、同じ文字を何度も書き換える無駄な処理を避けられます。また、剰余演算を適切に行うことで、大きなシフト量や整数オーバーフローにも対応できる堅牢な実装になります。同様の「区間への加算」を伴う問題では、この累積和（いもす法的な発想）のテクニックが応用できるので、ぜひ覚えておきましょう。