Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 225 ยท Strings

String Compression and Encoding Problems

Solve string compression and encoding problems in Python: run-length encoding, the LZ77 idea, Roman numerals and base conversion, with tests.

Many string problems are really about representation. The same information can be written in a short form or a long form, in one alphabet or another, and your job is to convert between them without losing anything. Run-length encoding squeezes repeated characters, LZ77 squeezes repeated phrases, Roman numerals write numbers with letters, and base conversion rewrites a number using a different set of digits.

These problems look different, but they share one skeleton: a scan that reads the input from left to right, a small piece of state (the current run, the current window, the running total), and a rule that decides what to emit. If you are comfortable with strings in Python and the classic string problems, this lesson shows how far the same ideas go. We will also ask, for every encoder, the question interviewers love: can we decode it back without ambiguity?

Run-length encoding, done safely

Classic String Problems showed the basic form, "aaabcc" to "a3b1c2". That format has a trap: if the input itself contains digits, the decoder cannot tell where a count ends. The text "a11" encodes as a112 (an a once, then a 1 twice), and a decoder that reads a followed by all the digits 112 believes it saw 112 a's.

The first example below shows the bug on purpose. It uses itertools.groupby, which groups consecutive equal items, and a naive decoder that reads a character followed by all the digits after it.

Python The digit trap in naive run-length encoding

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The fix is to make every run self-delimiting. Write the count, then a separator, then exactly one character. The decoder finds the first separator, reads the number before it, and takes the single character after it, whatever that character is.

Python An unambiguous format with a separator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Now "a11" becomes 1:a2:1, and even a string made of colons survives, because the decoder always takes exactly one character after the first colon it finds. Both functions are O(n) time.

Does it actually compress? RLE only helps when runs are long. For "abcd" the output 1:a1:b1:c1:d is three times longer. Production formats write a run only when it is worth it, or mark literals separately. In an interview, mention that you would return the original string when the encoded form is not shorter.

The LZ77 idea: point back at repeats

RLE only notices a single character repeated. Real compressors such as the ones behind ZIP and PNG notice that a phrase appeared earlier. The LZ77 family keeps a sliding window of recently seen text. At each position it looks for the longest match of the upcoming text inside the window, and instead of writing the text again it writes a token: how far back the match starts (the offset), how many characters it covers (the length), and the next literal character after the match.

flowchart LR
    A["Position i in the text"] --> B["Search the window<br/>for the longest match"]
    B --> C{"Match found?"}
    C -- yes --> D["Emit (offset, length, next char)"]
    C -- no --> E["Emit (0, 0, char)"]
    D --> F["Move i forward by length + 1"]
    E --> F
    F --> A

The LZ77 loop: find the longest earlier match, emit a token, advance past the match and the literal that follows.

The decoder is wonderfully simple. It rebuilds the text one token at a time: copy length characters starting offset positions back, then append the literal. A match may even overlap the text being written, which is how a short pattern repeats itself (offset 1, length 5 turns one a into six).

Python A tiny LZ77 encoder and decoder

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For "aaaaaaa" the encoder emits (0, 0, 'a') and then (1, 5, 'a'): "copy from one back, five times, then write an a". The decoder copies one character at a time, so each copy sees the character just appended; that is why overlapping matches work.

This version tries every start in the window, so it costs O(n * w * L) time for window size w and match length L. Real implementations use hash tables or suffix structures (see suffix structures and hash tables) to find candidates quickly. The point for an interview is the idea: a compressed stream is a mix of literals and back-references, and decoding is a trivial replay.

Roman numerals

Roman numerals use seven symbols: I=1, V=5, X=10, L=50, C=100, D=500, M=1000. Symbols are normally written from large to small and added. The twist is the subtractive form: a smaller symbol before a larger one is subtracted, so IV is 4 and XC is 90.

Roman to integer. Scan left to right. If the current value is smaller than the next one, subtract it, otherwise add it. One pass, O(n).

Integer to Roman. Use a table that includes the subtractive pairs (900, 400, 90, 40, 9, 4) in descending order, and take each value as many times as it fits. This is a small greedy algorithm (see greedy algorithms); it works because the table is built so that the largest piece always fits first.

Python Roman numerals in both directions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both directions are effectively constant time, because a Roman numeral has at most 15 symbols. Two interview follow-ups: validate a numeral (reject IIII or VX) by converting to an integer and back and comparing, and note that the greedy table only works because every needed subtractive pair is listed explicitly.

Base conversion

A number is a quantity; a base is just how we write it. To convert a non-negative integer to base b, repeatedly divide by b and collect the remainders. The remainders come out from the least significant digit upward, so reverse them at the end. To go the other way, walk the digits from the left and compute value = value * b + digit (Horner's rule).

flowchart TD
    A["n = 156, base 2"] --> B["156 / 2 = 78 remainder 0"]
    B --> C["78 / 2 = 39 remainder 0"]
    C --> D["39 / 2 = 19 remainder 1"]
    D --> E["19 / 2 = 9 remainder 1"]
    E --> F["9 / 2 = 4 remainder 1"]
    F --> G["4 / 2 = 2 remainder 0"]
    G --> H["2 / 2 = 1 remainder 0"]
    H --> I["1 / 2 = 0 remainder 1"]
    I --> J["Read remainders upward: 10011100"]

Dividing by the base repeatedly: the remainders, read from the last to the first, are the digits.

Digits above 9 need letters. A string of digit characters, "0123456789abcdefghijklmnopqrstuvwxyz", lets you use an index lookup both ways. Do not forget zero (the loop above would produce an empty string) and negative numbers.

Python Convert between any bases from 2 to 36

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time is O(d) for d digits, and d is about log base b of n. Python can do the common cases for you: bin, oct, hex, int(text, base) and the format spec format(n, "b"). In interviews, however, you are usually asked to write the loop yourself.

A related puzzle, the Excel column title, is a base conversion with a twist: it is bijective base 26 (A=1 to Z=26, with no zero digit), so you subtract 1 before each division. Writing that variant is a good test of whether you understand why the loop works, not just that it does.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is the format 'character followed by count' (for example a11) risky for run-length encoding?

    If the data itself contains digits, the decoder cannot tell where a count ends. A separator or a fixed layout makes the format unambiguous.
  2. 2. What does the LZ77 token (1, 5, 'a') mean when decoding?

    The offset is how far back to start copying, the length is how many characters to copy (they may overlap the text being written), and the literal is appended afterwards.
  3. 3. In roman_to_int, what do you do when the current symbol is smaller than the next one?

    A smaller value before a larger one is subtracted: IV is 5 - 1. Otherwise values are added.
  4. 4. When converting a number to another base by repeated division, in what order do the remainders appear?

    The first remainder is the lowest digit. Reverse the collected digits, or build the string from the front, to get the usual order.

Summary

  • Compression and encoding problems are scan-and-emit loops with a little state; always check that the output can be decoded back.
  • Run-length encoding only helps with long runs, and the format must stay unambiguous when the data contains digits; a separator solves that.
  • LZ77 replaces repeated phrases with (offset, length, literal) tokens; decoding is a simple replay that allows overlapping copies.
  • Roman numerals: subtract when a value is smaller than its right neighbour; convert back with a greedy table that includes the subtractive pairs.
  • Base conversion: divide and collect remainders (then reverse) one way, Horner's rule the other way; remember zero and negative numbers.

Next, switch from strings to pointers with Linked Lists.