B - Data Compression Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は、大量のログデータを効率よく保存するためのシンプルな圧縮アルゴリズムを実装することにしました。

高橋君が考えた圧縮ルールは以下の通りです：

英小文字からなる文字列 S が与えられたとき、連続する同じ文字の並びを「その文字1つ + 連続した個数」に置き換えます。ただし、連続が 1 個の場合は個数を省略し、文字のみを出力します。

例えば、文字列 aaabbc は以下のように圧縮されます：

  • aaa → a3（a が 3 個連続）
  • bb → b2（b が 2 個連続）
  • c → c（c が 1 個なので個数は省略）
  • 結果：a3b2c

この圧縮方式はランレングス圧縮と呼ばれ、同じ文字が連続して現れるデータに対して効果的です。

高橋君のために、与えられた文字列を上記のルールで圧縮した結果を出力してください。

制約

  • 1 \leq |S| \leq 2 \times 10^5
  • S は英小文字のみからなる

入力

S
  • 1 行目には、英小文字からなる文字列 S が与えられる。

出力

文字列 S を圧縮した結果を 1 行で出力せよ。

入力例 1

aaabbc

出力例 1

a3b2c

入力例 2

abcde

出力例 2

abcde

入力例 3

aaabbbbccdddddeeefghhhh

出力例 3

a3b4c2d5e3fgh4

入力例 4

zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbccccccccccddddddddddddeeeeeeeeeeffffffffgggggggggggggghhhhhhhhhiiiiiiiiiiijjjjjjjjkkkkkkkkkkklllllllllllmmmmmmmmmnnnnnnnnnnooooooooooppppppppppqqqqqqqqqqrrrrrrrrrrssssssssssttttttttttuuuuuuuuuuvvvvvvvvvvwwwwwwwwwwxxxxxxxxxxyyyyyyyyyyzzzzzzzzzz

出力例 4

z51a20b15c10d12e10f8g14h9i11j8k11l11m9n10o10p10q10r10s10t10u10v10w10x10y10z10

入力例 5

a

出力例 5

a

Score : 333 pts

Problem Statement

Takahashi decided to implement a simple compression algorithm to efficiently store a large amount of log data.

The compression rules Takahashi devised are as follows:

Given a string S consisting of lowercase English letters, replace each consecutive sequence of the same character with "that character once + the count of consecutive occurrences." However, if the count is 1, omit the count and output only the character.

For example, the string aaabbc is compressed as follows:

  • aaa → a3 (3 consecutive a's)
  • bb → b2 (2 consecutive b's)
  • c → c (only 1 c, so the count is omitted)
  • Result: a3b2c

This compression method is called run-length encoding, and it is effective for data where the same character appears consecutively.

For Takahashi, please output the result of compressing the given string according to the rules above.

Constraints

  • 1 \leq |S| \leq 2 \times 10^5
  • S consists only of lowercase English letters

Input

S
  • The first line contains a string S consisting of lowercase English letters.

Output

Output the result of compressing the string S in a single line.

Sample Input 1

aaabbc

Sample Output 1

a3b2c

Sample Input 2

abcde

Sample Output 2

abcde

Sample Input 3

aaabbbbccdddddeeefghhhh

Sample Output 3

a3b4c2d5e3fgh4

Sample Input 4

zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbccccccccccddddddddddddeeeeeeeeeeffffffffgggggggggggggghhhhhhhhhiiiiiiiiiiijjjjjjjjkkkkkkkkkkklllllllllllmmmmmmmmmnnnnnnnnnnooooooooooppppppppppqqqqqqqqqqrrrrrrrrrrssssssssssttttttttttuuuuuuuuuuvvvvvvvvvvwwwwwwwwwwxxxxxxxxxxyyyyyyyyyyzzzzzzzzzz

Sample Output 4

z51a20b15c10d12e10f8g14h9i11j8k11l11m9n10o10p10q10r10s10t10u10v10w10x10y10z10

Sample Input 5

a

Sample Output 5

a