Overview

Given a string \(S\), this problem asks you to perform “run-length encoding (RLE),” which replaces consecutive sequences of the same character with the format “character + count.” However, there is a rule that the count is omitted when it is 1.

Analysis

The key point for solving this problem is to accurately identify “where character transitions occur.”

For example, consider the string aaabbc: 1. a appears 3 times consecutively (aaa) → a3 2. Next, b appears 2 times consecutively (bb) → b2 3. Next, c appears only once (c) → c (the 1 is omitted)

Since the length \(|S|\) of the string can be up to \(2 \times 10^5\), which is relatively large, we need to scan the string character by character from the beginning and process it efficiently.

Efficient String Operations

In languages like Python, repeatedly concatenating strings (s = s + "a") creates a new string object each time, resulting in \(O(|S|^2)\) computation time, which may exceed the time limit (TLE). Therefore, it is more efficient to store results in a list and join them all at once at the end ("".join(list)), or to use regular expressions or iterators.

Algorithm

An approach using Regular Expressions is very concise.

1. Pattern Construction: To find consecutive runs of the same character, we use the regular expression ([a-z])\1*.
   • ([a-z]) : Captures any single lowercase English letter and assigns it to group 1.
   • \1* : Matches zero or more repetitions of the same character that was matched in group 1.
2. Executing the Matching: By using re.finditer, we can sequentially extract all portions (runs) of the string that match this pattern.
3. Conversion: For each match, we convert it to a string according to the following rules:
   • Get the type of the consecutive character using m.group(1).
   • Get the total length (consecutive count) using len(m.group(0)).
   • If the length is greater than 1, output “character + length”; if it is 1, output only the “character”.
4. Concatenation and Output: Concatenate all the resulting parts and output the result.

Complexity

• Time Complexity: \(O(|S|)\) Since we scan the string once to perform matching, the processing completes in time proportional to the length of the string.
• Space Complexity: \(O(|S|)\) Memory is needed to store the compressed string.

Implementation Notes

• Utilizing Regular Expressions: By using re.finditer, we can extract “groups of identical characters” more concisely and efficiently than writing our own loop logic.

• Count Checking: By writing the conditional branch if len > 1 using a ternary operator or similar construct, we can elegantly handle the special case where the count is 1 (i.e., not writing the number).

• Fast I/O: By using sys.stdin.read().strip() and sys.stdout.write, we ensure the solution runs efficiently even with large amounts of data.

  Source Code

import re
import sys

def solve():
    # 標準入力から文字列Sを読み込みます
    # sys.stdin.read().strip() を使用することで、末尾の改行や空白を除去します
    s = sys.stdin.read().strip()
    
    if not s:
        return

    # 正規表現を使用して、同じ文字が連続する部分（ラン）を抽出します。
    # ([a-z]) : 英小文字1文字をキャプチャし、グループ1とします。
    # \1*     : グループ1と同じ文字が0回以上繰り返される部分にマッチします。
    # re.finditer はマッチした各部分をイテレータとして返します。
    matches = re.finditer(r'([a-z])\1*', s)

    # 各マッチオブジェクト m に対して以下の処理を行います：
    # m.group(1) : 連続する文字の種類の1文字目
    # m.group(0) : マッチした文字列全体（例: "aaa"）
    # len(m.group(0)) : その文字が連続している個数
    # 個数が1より大きい場合は「文字 + 個数」、1の場合は「文字」のみをリストに追加します。
    result = (m.group(1) + (str(len(m.group(0))) if len(m.group(0)) > 1 else "")
              for m in matches)

    # 最後にすべての結果を連結して出力します
    sys.stdout.write("".join(result) + "\n")

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.