PythonMediumStrings20 min

Compress consecutive character runs

Input contains lowercase English letters only. Keep separate runs separate, and always include a count even when it is one. Interviewers use this problem to assess advance an end pointer across each equal-character run.

Input

One line of lowercase letters.

Output

Print the result on one line; print an empty line for an empty string.

Constraints

0 <= length <= 100000.

Example

Input

aabccc

Output

a2b1c3

Example 2 input

abbba

Output

a1b3a1

Matching letters in nonadjacent runs stay separate.

Public test cases (2)

Input
```
aabccc
```
Expected output
```
a2b1c3
```
Input
```
ababa
```
Expected output
```
a1b1a1b1a1
```

Hints (2)

Identify the state needed to avoid repeated work.
Advance an end pointer across each equal-character run.

Target complexity: time O(n) · space O(n)

Your solution

import sys


def solve_run_length_compression(s):
    # your code
    return ""


if __name__ == "__main__":
    data = sys.stdin.read()
    s = data.split("\n", 1)[0]
    result = solve_run_length_compression(s)
    print(result)

Standard input

Checking runner availability…

Reference solution

Check whether a number is prime · Easy
Check whether a string is a palindrome · Easy
Check whether two strings are anagrams · Easy
Compute the factorial of a number · Easy
Count vowels and consonants · Easy
Find the first occurrence with binary search · Easy
Find the missing number from zero through n · Easy
Find the second largest distinct value · Easy
Generate the Fibonacci series · Easy
Remove duplicate values while preserving order · Easy

All Python programs

Compress consecutive character runs

Input

Output

Constraints

Example

Public test cases (2)

Your solution

Reference solution

More Python programs