概要

与えられた文字列に対して、連続する同じ文字を「文字 + 個数」の形式に圧縮するランレングス圧縮を実装する問題です。

考察

問題の本質

この問題では、文字列を左から右へ走査しながら、同じ文字が何個連続しているかを数える必要があります。

具体例で理解する

文字列 aaabbc を例に考えてみましょう：

位置:  0 1 2 3 4 5
文字:  a a a b b c

1. 位置 \(0\) から開始：a が位置 \(0, 1, 2\) で \(3\) 個連続 → a3
2. 位置 \(3\) から開始：b が位置 \(3, 4\) で \(2\) 個連続 → b2
3. 位置 \(5\) から開始：c が位置 \(5\) で \(1\) 個のみ → c（個数省略）
4. 結果を連結：a3b2c

なぜ素朴なアプローチでも大丈夫か

この問題では、各文字は最大でも1回しか走査されません。連続する文字を数え終わったら、その分だけインデックスを進めるため、文字列全体を1回走査するだけで済みます。したがって、素朴な実装でも十分高速です。

アルゴリズム

1. 初期化: 結果を格納するリストと、現在位置を示すインデックス \(i\) を用意
2. ループ処理: 文字列の先頭から末尾まで以下を繰り返す
   • 現在位置の文字 char を記録
   • 同じ文字が何個連続するか count を数える
   • count が \(1\) なら文字のみ、\(2\) 以上なら「文字 + 個数」を結果に追加
   • インデックス \(i\) を count だけ進める
3. 出力: 結果リストを連結して出力

連続個数のカウント方法

while i + count < n and S[i + count] == char:
    count += 1

この部分で、現在の文字 char と同じ文字が続く限り count を増やしています。

計算量

• 時間計算量: \(O(|S|)\)
  • 各文字は最大1回だけ参照されるため、文字列の長さに比例
• 空間計算量: \(O(|S|)\)
  • 結果を格納するリストのサイズは、最悪の場合（全て異なる文字）で元の文字列と同じ長さ

実装のポイント

1. インデックスの更新: 連続する文字をカウントした後、i += count でまとめてインデックスを進める。i += 1 としてしまうと同じ文字を重複して処理してしまうので注意。

2. 文字列の連結: Pythonでは文字列を + で繰り返し連結すると遅くなるため、リストに追加してから最後に ''.join() で連結するのが効率的。

3. 個数が1の場合の処理: 問題文の指示通り、連続が \(1\) 個の場合は数字を付けずに文字のみを出力する。

   ソースコード

S = input()

result = []
i = 0
n = len(S)

while i < n:
    char = S[i]
    count = 1
    while i + count < n and S[i + count] == char:
        count += 1
    if count == 1:
        result.append(char)
    else:
        result.append(char + str(count))
    i += count

print(''.join(result))

---

この解説は claude4.5opus によって生成されました。