Introduction

Run-length encoding compresses repeated characters by replacing a run with a shorter representation. If the goal is the minimum encoded length, the first thing to pin down is the encoding format, because the answer depends entirely on how a run is written.

Define The Encoding Rule First

A common compact rule is:

• write just the character for a run of length 1
• write the character followed by the count for runs longer than 1

Under that rule:

• 'A stays A'
• 'AA becomes A2'
• 'AAAAB becomes A4B'

If you instead force every run to include the count, even singletons become longer and the "minimum" answer changes.

Why The Minimum Length Is Mostly Determined

For a fixed RLE format and a fixed input string, there is usually no search problem at all. The best encoding is simply the natural run partition of the string.

For example, for:

AAABBCA

the natural runs are:

• 'AAA'
• 'BB'
• 'C'
• 'A'

So the minimal encoded form under the compact rule is:

A3B2CA

and its length is 6.

A Simple Implementation

Here is a Python function that computes both the encoded string and its length.

1def rle_encode(s):
2    if not s:
3        return ""
4
5    parts = []
6    run_char = s[0]
7    run_length = 1
8
9    for ch in s[1:]:
10        if ch == run_char:
11            run_length += 1
12        else:
13            if run_length == 1:
14                parts.append(run_char)
15            else:
16                parts.append(f"{run_char}{run_length}")
17            run_char = ch
18            run_length = 1
19
20    if run_length == 1:
21        parts.append(run_char)
22    else:
23        parts.append(f"{run_char}{run_length}")
24
25    return "".join(parts)
26
27
28encoded = rle_encode("AAABBCA")
29print(encoded)
30print(len(encoded))

This runs in linear time because each character is processed once.

Compute The Length Without Building The Output

If you only need the minimum length, you can count it directly.

1def rle_length(s):
2    if not s:
3        return 0
4
5    total = 0
6    run_char = s[0]
7    run_length = 1
8
9    for ch in s[1:]:
10        if ch == run_char:
11            run_length += 1
12        else:
13            total += 1 if run_length == 1 else 1 + len(str(run_length))
14            run_char = ch
15            run_length = 1
16
17    total += 1 if run_length == 1 else 1 + len(str(run_length))
18    return total
19
20
21print(rle_length("AAABBCA"))
22print(rle_length("AAAAAAAAAAA"))

The second example is useful because counts with two or more digits change the encoded length. A run of length 9 uses one digit, while a run of length 10 uses two.

Why Digit Boundaries Matter

When a run grows from:

• '1 to 2, the encoded length jumps because you start writing a count'
• '9 to 10, the encoded length increases again'
• '99 to 100, it increases again'

That is why compression algorithms or dynamic-programming variants that modify the string often pay special attention to these thresholds.

If The Problem Includes String Modification

Some algorithm problems use the phrase "minimum length RLE" for a harder task: you may be allowed to delete or alter characters before encoding. In that version, the problem is no longer a single left-to-right scan. It becomes a dynamic-programming optimization problem because changing one character can merge or split runs.

If deletions are allowed, the naive linear approach above is not enough. But if the string is fixed and the encoding rule is fixed, the minimum-length encoding is simply the natural run-length encoding.

Common Pitfalls

A common mistake is encoding single characters as A1, B1, and so on when the problem definition expects singletons to stay as plain characters. That inflates the result and makes the length non-minimal.

Another issue is ignoring digit growth. A run of 12 characters does not contribute length 2; it contributes the character plus two count digits.

Developers also sometimes assume there is a complex optimization problem when the input string is fixed. For standard RLE, there usually is not. One pass over the natural runs is enough.

Finally, be explicit about the encoding format before implementing anything. "Minimum length" is meaningless until the representation rule is fixed.

Summary

• Minimum-length RLE depends on the exact encoding rule.
• For a fixed string and a fixed standard RLE format, the minimal encoding is the natural run partition.
• A single linear scan is enough to compute the encoded string or just its length.
• Pay attention to count-digit boundaries such as 9 to 10.
• If the problem allows deletions or edits before encoding, it becomes a different and harder optimization problem.