Full lesson preview

Implement Run-Length Encoding

Compress a string by encoding consecutive repeated characters as (character, count) pairs.

Python practice30 minLoops & IterationAdvancedLast updated March 15, 2026

Problem statement

Run-length encoding (RLE) is a simple compression technique that replaces consecutive repeated characters with a pair (character, count). Implement a function run_length_encode(s) that takes a string s and returns a list of tuples, where each tuple contains a character from the string and the number of times it repeats consecutively. The order of runs must be the same as they appear in the input string. If the input is an empty string, return an empty list. You must implement this using loops (for/while) and not use external libraries or Python utilities like itertools.groupby. The function should be linear in the length of the input string.

Task

Write a function that scans a string and returns a list of tuples representing consecutive character runs and their lengths (basic run-length encoding).

Examples

Basic example

Input

run_length_encode('AAAABBBCCDAA')

Output

[('A', 4), ('B', 3), ('C', 2), ('D', 1), ('A', 2)]

The input has four A's, then three B's, two C's, one D, and two A's at the end. Each consecutive run is emitted as a tuple (character, count).

Input format

A single string argument s passed to run_length_encode(s).

Output format

A list of tuples: [(char1, count1), (char2, count2), ...]. For an empty input string, return [].

Constraints

Do not use external libraries or itertools.groupby. Use loops to scan the string. Time complexity should be O(n) where n is the length of the string. Preserve the original order of runs.

Samples

Sample 1

Input

run_length_encode('XYZ')

Output

[('X', 1), ('Y', 1), ('Z', 1)]

Each character appears once, so each run has count 1.