Implement Run-Length Encoding

Summary

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

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

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