概要

文字列 \(S\) を左から見て、同じ文字が連続する区間ごとに「文字 + 連続回数（ただし \(1\) 回なら省略）」へ置き換えるランレングス圧縮を行います。

考察

重要なのは、「圧縮結果は“連続する同一文字のまとまり（区間）”ごとに独立に決まる」という点です。
例えば aaabbc は aaa, bb, c という3つの区間に分けられ、それぞれを a3, b2, c に変換して連結すれば答えになります。

素朴に「各位置から先を見て連続数を数える」実装を、毎回部分文字列操作や不要な探索で行うと、最悪で同じ場所を何度も調べてしまい \(O(|S|^2)\) になり得ます（長さが \(2\times 10^5\) なのでTLEの原因になります）。
そこで、文字列を 1回だけ 左から走査し、連続区間をまとめて処理すれば \(O(|S|)\) で解けます。

アルゴリズム

Python の itertools.groupby を使うと、「隣り合う同じ要素」をひとまとめにして順に取り出せます。

1. groupby(S) で、(文字 ch, その文字が連続する部分を走査するイテレータ grp) を順に得る。
2. grp から要素数を数えて連続回数 cnt を求める。
3. cnt == 1 なら ch のみ、そうでなければ ch + str(cnt) を出力用配列に追加。
4. 最後に配列を "".join(...) で連結して出力。

例：S = "aaabbc"
- ('a', "aaa") → cnt=3 → "a3"
- ('b', "bb") → cnt=2 → "b2"
- ('c', "c") → cnt=1 → "c"
連結して "a3b2c" になります。

計算量

• 時間計算量: \(O(|S|)\)（各文字をちょうど1回ずつ数える）
• 空間計算量: \(O(|S|)\)（出力文字列分。作業用は区間ごとに定数）

実装のポイント

• groupby の grp は一度しか走査できないイテレータなので、個数を数える処理（ここでは sum(1 for _ in grp)）は1回で済ませます。

• 文字列の逐次連結（ans += ... を大量に行う）は遅くなりやすいので、list に追加して最後に join するのが安全です。

• 入力サイズが大きいので sys.stdin.readline() を使うと高速です。

  ソースコード

import sys
from itertools import groupby

S = sys.stdin.readline().strip()

out = []
for ch, grp in groupby(S):
    cnt = sum(1 for _ in grp)
    out.append(ch if cnt == 1 else f"{ch}{cnt}")

sys.stdout.write("".join(out))

この解説は gpt-5.2-high によって生成されました。