概要

与えられた英小文字のみからなる文字列に対し、連続する同じ文字を「文字+個数」の形式に圧縮する問題です。ただし、個数が1の場合は数字を省略します。

考察

この問題は、文字列を先頭から順に見ていき、「連続している同じ文字の区間」を見つけ出す必要があります。
例えば aaabbc の場合：

• 最初の a は3つ連続 → a3
• 次の b は2つ連続 → b2
• 最後の c は1つだけ → c

素朴な方法として、各文字についてその次の文字が同じかどうかを確認しながらカウントしていくことが考えられます。
しかし、全探索的に1文字ずつ数えると、最悪ケースで非常に非効率になります。特に文字数が多いときにTLEしないよう、線形時間で処理できるようにしたいです。

この問題では、尺取り法（しゃくとり法）と呼ばれるテクニックが有効です。
左端 \(l\) と右端 \(r\) の2つのポインタを使って、現在注目している連続区間を管理します。
\(r\) を進めながら、次に違う文字にぶつかった時点で区間を確定させ、結果に追加し、次の区間を開始します。

このようにすることで、文字列全体を一度だけ見て、効率良く圧縮結果を得ることができます。

アルゴリズム

1. 文字列 \(S\) を入力として受け取る。
2. 結果を格納するリスト res を用意する。
3. 左端を示す変数 l を初期化（最初は0）。
4. 右端を示す変数 r を for ループで 0 から \(|S|-1\) まで動かす。
5. 各ステップで、以下の条件を判定する：
   • r が文字列の最後の位置にある、または
   • S[r] と S[r+1] が異なる文字である
6. 上記条件を満たす場合：
   • 現在の区間 [l, r] の長さ cnt = r - l + 1 を計算する。
   • cnt が 1 なら文字のみ、それ以外なら「文字 + 個数」を res に追加。
   • 次の区間のために l = r + 1 を設定。
7. 最後に res を連結して出力。

例: aaabbc の処理

最終的な結果: "a3b2c"

計算量

• 時間計算量: \(O(|S|)\) — 各文字を一度だけ参照する。
• 空間計算量: \(O(|S|)\) — 圧縮結果を格納するリストのサイズは最大で \(|S|\) 程度。

実装のポイント

• 区間の終端を判定する際に、r == len(S) - 1 のチェックを忘れないこと（インデックスエラー回避）。

• 文字列結合には "".join(res) を使うことで効率的に連結できる。

• cnt == 1 のときは数字を省略する点に注意。

  ソースコード

S = input()

res = []
l = 0
for r in range(len(S)):
    if r == len(S) - 1 or S[r] != S[r + 1]:
        cnt = r - l + 1
        res.append(S[l] + ("" if cnt == 1 else str(cnt)))
        l = r + 1

print("".join(res))

この解説は qwen3-coder-480b によって生成されました。