Overview

This is a problem where you implement run-length encoding, which compresses consecutive identical characters in a given string into the format “character + count”.

Analysis

Essence of the Problem

In this problem, you need to scan the string from left to right and count how many consecutive identical characters there are.

Understanding with a Concrete Example

Let’s consider the string aaabbc as an example:

Position:  0 1 2 3 4 5
Character: a a a b b c

1. Starting at position \(0\): a appears \(3\) times consecutively at positions \(0, 1, 2\) → a3
2. Starting at position \(3\): b appears \(2\) times consecutively at positions \(3, 4\) → b2
3. Starting at position \(5\): c appears only \(1\) time at position \(5\) → c (count omitted)
4. Concatenate the results: a3b2c

Why a Naive Approach Works Fine

In this problem, each character is scanned at most once. After counting consecutive characters, the index advances by that amount, so we only need a single pass through the entire string. Therefore, even a naive implementation is sufficiently fast.

Algorithm

1. Initialization: Prepare a list to store the result and an index \(i\) indicating the current position
2. Loop Processing: Repeat the following from the beginning to the end of the string
   • Record the character char at the current position
   • Count how many consecutive identical characters there are as count
   • If count is \(1\), add only the character; if \(2\) or more, add “character + count” to the result
   • Advance the index \(i\) by count
3. Output: Concatenate the result list and output it

Method for Counting Consecutive Characters

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

This part increments count as long as the same character char continues.

Complexity

• Time Complexity: \(O(|S|)\)
  • Since each character is referenced at most once, it is proportional to the length of the string
• Space Complexity: \(O(|S|)\)
  • The size of the list storing the result is, in the worst case (all different characters), the same length as the original string

Implementation Notes

1. Index Update: After counting consecutive characters, advance the index all at once with i += count. Be careful not to use i += 1, as this would result in processing the same characters redundantly.

2. String Concatenation: In Python, repeatedly concatenating strings with + is slow, so it is more efficient to append to a list and then concatenate at the end with ''.join().

3. Handling a Count of 1: As specified in the problem statement, when there is only \(1\) consecutive character, output only the character without appending a number.

   Source Code

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

---

This editorial was generated by claude4.5opus.