Overview

We scan the string \(S\) from left to right and perform run-length encoding, replacing each maximal run of consecutive identical characters with “character + count (omitting the count if it is \(1\))”.

Analysis

The key observation is that “the compression result is determined independently for each run (maximal interval of consecutive identical characters).”
For example, aaabbc is divided into three runs: aaa, bb, c, and converting each to a3, b2, c respectively and concatenating them gives the answer.

A naive implementation that “looks ahead from each position to count consecutive characters,” potentially re-examining the same positions multiple times due to unnecessary substring operations or redundant searches, can be \(O(|S|^2)\) in the worst case (which causes TLE since the length can be up to \(2\times 10^5\)).
Instead, by scanning the string exactly once from left to right and processing each run together, we can solve it in \(O(|S|)\).

Algorithm

Using Python’s itertools.groupby, we can group consecutive identical elements and iterate over them in order.

1. Use groupby(S) to obtain pairs (character ch, iterator grp over the consecutive run of that character) in order.
2. Count the number of elements from grp to get the run length cnt.
3. If cnt == 1, append only ch; otherwise append ch + str(cnt) to the output list.
4. Finally, concatenate the list with "".join(...) and output.

Example: S = "aaabbc"
- ('a', "aaa") → cnt=3 → "a3"
- ('b', "bb") → cnt=2 → "b2"
- ('c', "c") → cnt=1 → "c"
Concatenating gives "a3b2c".

Complexity

• Time complexity: \(O(|S|)\) (each character is counted exactly once)
• Space complexity: \(O(|S|)\) (for the output string; working space per run is constant)

Implementation Notes

• The grp from groupby is a single-pass iterator, so the counting operation (here sum(1 for _ in grp)) must be done in one pass.

• Repeatedly concatenating strings (ans += ... many times) can be slow, so it is safer to append to a list and join at the end.

• Since the input size can be large, using sys.stdin.readline() is faster.

  Source Code

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))

This editorial was generated by gpt-5.2-high.