DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 58: Python Run-Length Encoding (RLE) – Compress Strings Like a Pro with This Ultra-Simple O(n) Trick

#challenge #python #intermediate #programming

Welcome to Day 58 of the #80DaysOfChallenges journey! This intermediate challenge implements Run-Length Encoding (RLE), the classic compression technique that turns "AAAAABBBCC" into "A5B3C2". It's the same method used in fax machines, BMP images, and even some game formats, and it's shockingly effective for data with long runs of repeated characters.

The solution is pure, readable, and runs in perfect O(n) time with O(1) extra space (beyond output). No libraries, no complexity, just clean Python that works.

If you're into compression, data encoding, or just love seeing long strings shrink dramatically, this "Python RLE compressor" is beautiful, practical, and instantly useful.

Example:

"WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB" → "W12B1W12B3W24B1"

💡 Key Takeaways from Day 58: RLE Encoder Function

This challenge delivers a flawless RLE implementation that counts consecutive characters and builds the compressed string in one pass. We'll break it down: empty string handling, run detection with counter, final run append, and interactive main.

1. Function Design: Immediate Empty Check 

def rle_encode(text: str) -> str:
    if not text:
        return ""

    result = []
    count = 1
Enter fullscreen mode Exit fullscreen mode

Returns empty string for empty input, perfect. Initializes result list (for efficient building) and count=1 (since single char = run of 1).

2. Core Loop: Run Detection Magic 

    for i in range(1, len(text)):
        if text[i] == text[i - 1]:
            count += 1
        else:
            result.append(f"{text[i - 1]}{count}")
            count = 1
Enter fullscreen mode Exit fullscreen mode

This is the heart:

  • If current char == previous, increment count
  • Else, close current run and start new one with count=1

For "AAA": i=1 (A==A) → count=2; i=2 (A==A) → count=3 → loop ends → final append "A3"

3. Final Run: Never Forget the Last Group! 

    # Handle the final run
    result.append(f"{text[-1]}{count}")

    return "".join(result)
Enter fullscreen mode Exit fullscreen mode

The loop misses the last run, so we always append it at the end. Classic pattern in run-based algorithms.

4. Main Interactive: Real Testing 

user_input = input("Enter a string to encode: ").strip()

if user_input == "":
    print("No input provided. Exiting.")
    else:
    encoded = rle_encode(user_input)
    print(f"Encoded (RLE): {encoded}")
Enter fullscreen mode Exit fullscreen mode

Clean input, immediate compression result. Try "aaaabbbcca" → "a4b3c2a1"

🎯 Summary and Reflections

This RLE encoder is short, perfect, and teaches one of the most useful patterns in data compression: run detection with counter reset. It reinforced:

  • Always handle the final run separately: Common in all run-length algorithms
  • List + join beats string +=: O(n) vs O(n²) for long runs
  • Real compression power: "A"×1000000 becomes "A1000000", tiny!

This exact technique is used in PNG, TIFF, and even some video codecs.

Advanced Alternatives:

  • Decode function (RLE is reversible!)
  • Handle numbers in input (current version treats "111" as three '1's)
  • Binary RLE for files

But this version is production-ready for text with repeats.

🚀 Next Steps and Resources

Day 58 gave you real compression power in 15 lines. Try compressing your name repeated 1000 times!

What's the longest run you ever compressed? Drop your wildest string below! 🔥

Top comments (0)