Compression and interview problems with Python strings

Why it matters

Three problems in this lesson come back in string interviews again and again. They use the tools you already have: counting, a loop that keeps state from one step to the next, and a moving window. They also teach you to explain your answer out loud. An interviewer who asks for the longest substring without repeats is listening for your plan, your complexity and your edge cases, not only for correct code. If you can explain each of these three problems in about two minutes, with the pattern named and the cost stated, you are ready for most string rounds.

Compression is also a real-world task. Image formats, fax machines and older archive tools store long runs of the same value as a count, because it is smaller than the raw data. Decompression is the reverse, and it is a good exercise in reading a format one piece at a time.

The idea: three patterns

Each problem in this lesson is an example of a pattern you can reuse.

• Scan the runs. Walk the text once and group neighbouring equal characters. Compression and decompression both use this idea.
• Count, then scan. Count every character in one pass, then look for the answer in a second pass. The first unique character uses this.
• Sliding window. Keep a range of the text, called a window, that has a property you care about. Move the right edge forward to grow it, and move the left edge forward to restore the property. The longest substring without repeats uses this.

The table at the end of this lesson lists the clues that point to each pattern. Learn to hear the clue in the question, because that is the step most candidates skip.

Run-length compression

Run-length encoding replaces each run of the same character with that character and the length of the run. A run is a block of equal characters that sits next to each other. For example, aabcccccaaa has four runs: aa, b, ccccc and aaa. Writing each run as its letter and its length gives a2b1c5a3. The two groups of a stay separate, because the b between them is a different run.

The picture in words: eleven characters, grouped into four runs, with one label per run. The first run covers two characters, so its label is a2. The second covers one character, so its label is b1. The third covers five, so its label is c5, and the last covers three with the label a3. The run count is the number of pairs in the output, not the number of letters.

The method walks the string with an index i that marks the start of the current run. A second index j moves forward while the characters match. When j stops, the run from i to j - 1 is complete. Write its letter and its length, then move i to j to start the next run.

import sys
 
def compress(s):
    parts = []
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1
        parts.append(s[i])
        parts.append(str(j - i))
        i = j
    encoded = "".join(parts)
    return encoded if len(encoded) < len(s) else s
 
for line in sys.stdin:
    print(compress(line.rstrip("\n")))

Type these lines in the input, one per line:

aabcccccaaa
abc
zzzzzzzzzzzz

The output is:

a2b1c5a3
abc
z12

Trace the first line. i starts at 0, the first a. j moves to 1, where the character is still a, so j moves to 2, where the character is b, and the inner loop stops. The run is j - i = 2 characters long, so the code writes a2. Then i becomes 2, the b. The next run is one character long, so it writes b1. The third run starts at index 3, and j moves until index 8, which gives c5. The last run is aaa, which gives a3. The output a2b1c5a3 has 8 characters, and the input had 11, so the compressed form is shorter and it is returned.

The second line, abc, has three runs of length one. Its encoding is a1b1c1, which has 6 characters, longer than the 3 in the input. The final check returns the original string, because the rule says to keep the shorter form. This check is a common interview detail, and it is worth saying out loud: "if compression does not help, return the input".

Counts can have more than one digit, and the encoding handles them without any extra code. The input zzzzzzzzzzzz, with twelve z characters, encodes to z12. That is three characters against twelve, so the encoded form is used. The decompression function below reads z12 back as twelve z characters, which is why the two functions form a matching pair.

The loop ends when i reaches the end of the string. It does not need a special case for the last run, because the inner loop always stops at the end and i then moves past it. This is one of the most common bugs in run-length code, so it is worth knowing the failure mode, which the common mistakes section covers.

The cost is O(n) time, because each character is visited once by the inner loop and once more by the outer loop as the start of a run. The extra space is O(n) for the list of pieces.

A line traced step by step

Traces are the best way to check a loop you do not fully trust. Take the input aabbbc, which has six characters at indexes 0 to 5. The table below follows the outer loop, where i marks the start of a run, and the inner loop, where j finds its end.

After step 3, i equals 6, the length of the input, so the outer loop stops. The encoding a2b3c1 has six characters, the same as the input. The final test is len(encoded) < len(s), which is 6 < 6, and that is false. The function therefore returns the original aabbbc. Call the compress function from this section on that input, with two prints added after the loop:

print(compress("aabbbc"))
print(compress("aabbbc") == "aabbbc")

The output is:

aabbbc
True

The strict < matters. An encoding that is the same length is not an improvement, so the original is kept. If you wrote <= instead, the function would return a2b3c1 for this input, which is not wrong, but it would make the output less predictable for a reader who expects the original whenever compression does not save space. Pick the rule the problem asks for, and say it out loud when you explain your answer.

A second window: at most two distinct letters

The sliding window is not limited to "no repeats". Change the property and the same moves solve a new problem. Suppose you need the longest substring that contains at most two different letters. The window now holds a count of each letter and a count of how many different letters it holds. Move the right edge to add a letter. While the window has three different letters, move the left edge to remove a letter, until only two remain.

Trace eceba, which has five characters at indexes 0 to 4.

• At i = 0 the window is e, with one distinct letter. The best length is 1.
• At i = 1 the window is ec, with two distinct letters. The best length is 2.
• At i = 2 the window is ece, still two distinct letters, because e is already counted. The best length is 3.
• At i = 3 the letter b makes three distinct letters. Move start past the e at index 0. The e still appears at index 2, so the window still has three letters. Move start past the c at index 1, which removes the last c. The window is now eb at indexes 2 and 3, with two letters. The best length stays 3.
• At i = 4 the letter a makes three distinct letters again. Move start past the e at index 2, which removes the last e. The window is ba, with two letters. The best length stays 3.

The answer is 3, for the window ece. The code uses collections.Counter, which keeps a count per key and returns 0 for a missing key:

from collections import Counter
 
def longest_two_distinct(s):
    counts = Counter()
    start = 0
    best = 0
    for i, c in enumerate(s):
        counts[c] += 1
        while len(counts) > 2:
            counts[s[start]] -= 1
            if counts[s[start]] == 0:
                del counts[s[start]]
            start += 1
        best = max(best, i - start + 1)
    return best
 
print(longest_two_distinct("eceba"), longest_two_distinct(""), longest_two_distinct("aaaa"))

The output is:

3 0 4

The cost is O(n), because each edge moves forward only, and each letter enters and leaves the window once. The idea to remember is that the window stores counts, not only positions, because it must know when a letter has really left. The line del counts[s[start]] matters. Without it, len(counts) would still count a letter whose count is 0, and the window would shrink too far.

Decompression

Decompression reads the encoding back into the original text. Each piece is a letter followed by a count, and the count can have more than one digit. The program has to read the digits as a single number, so a12 means twelve a characters, not an a followed by a 1 and a 2.

import sys
 
def decompress(s):
    parts = []
    i = 0
    while i < len(s):
        ch = s[i]
        i += 1
        count = 0
        while i < len(s) and s[i].isdigit():
            count = count * 10 + int(s[i])
            i += 1
        parts.append(ch * count)
    return "".join(parts)
 
for line in sys.stdin:
    print(decompress(line.rstrip("\n")))

Type these lines in the input:

a2b1c5a3
x12
a10

The output is:

aabcccccaaa
xxxxxxxxxxxx
aaaaaaaaaa

The trick is the inner loop that reads digits. After the letter is taken, the loop reads every digit that follows and builds the number. The line count = count * 10 + int(s[i]) is the same idea as the reversed-number trick from the palindrome lesson. int("7") is 7, and the loop turns each digit character into its value. For x12, the first digit gives count = 1, and the second gives count = 1 * 10 + 2 = 12.

Decompression assumes the input is well-formed: every letter is followed by a count. A letter with no count would get a count of 0 and disappear from the output. If the problem allows that, make the default count 1 instead of 0. Always confirm the format before writing the loop, because the loop trusts it.

The cost is O(n + total output length), because the program reads each input character once and writes each output character once. The "".join call at the end is one pass over the pieces, and ch * count builds each piece in one step.

The first non-repeating character

The next problem asks for the position of the first character that appears exactly once. For leetcode the answer is 0, because l appears once and comes first. For loveleetcode the answer is 2, because l, o and e repeat, and v is the first letter that appears once.

A single left-to-right scan cannot answer this. When you see l at index 0, you do not yet know whether a later l will appear. The standard method uses two passes. The first pass counts every letter. The second pass walks the string from the left and returns the index of the first letter whose count is 1.

import sys
 
def first_unique(s):
    count = {}
    for ch in s:
        count[ch] = count.get(ch, 0) + 1
    for i, ch in enumerate(s):
        if count[ch] == 1:
            return i
    return -1
 
for line in sys.stdin:
    print(first_unique(line.rstrip("\n")))

Type these three lines in the input:

leetcode
loveleetcode
aabb

The output is:

0
2
-1

The first pass fills the dict count, which holds the number of times each character appears. The method count.get(ch, 0) returns 0 for a character that is not in the dict yet, so the first sighting starts at 1. For loveleetcode the counts are l 2, o 2, v 1, e 4, t 1, c 1 and d 1. The second pass looks at each index in order: l has count 2, so it is skipped; o has count 2, skipped; v has count 1, so the function returns index 2. The -1 answer covers the case where every letter repeats, as in aabb.

Why does the second pass need the original string rather than the dict? The dict tells you counts, but not order. Order is what the problem asks for. The second pass gives you order back.

The cost is O(n) time and O(k) extra space, where k is the number of distinct characters. For plain lowercase English that is at most 26 keys. A fixed list of 26 integers, as used in the anagram lesson, does the same job with less overhead, but it works only for a to z. The dict works for any character.

For the last unique character, the same two passes work with the second pass run from the right. The fourth practice exercise asks you to write it.

The longest substring without repeats

This is the most important problem in the lesson, because it introduces the sliding window. The question asks for the length of the longest substring that has no repeated letter. For abcabcbb the answer is 3, for the window abc. For bbbbb it is 1. For pwwkew it is 3, for wke.

A sliding window is a range of the string described by two indexes: start for the left edge and i for the right edge. The window always has the property you want, which is that no letter repeats inside it. Move i to the right to add one letter. If the new letter already appears inside the window, move start forward until the window is clean again. Keep the largest window size you ever see.

The window is the two-pointer pattern in motion. Both edges move forward, and neither edge ever moves backward. In abcabcbb, the first window is abc, length 3. When the right edge reaches the second a, that a is already inside the window, so the left edge moves past the first a, and the window becomes bca. Then a repeated c moves the left edge again.

To know where the left edge must jump, store the last index where each letter appeared. A dict does that, and it works for any character. Each entry is a character and the index where it was last seen.

Here is the program. It reads one line per test and prints the length for each.

import sys
 
def longest_unique(s):
    last = {}
    start = 0
    best = 0
    for i, c in enumerate(s):
        if last.get(c, -1) >= start:
            start = last[c] + 1
        last[c] = i
        best = max(best, i - start + 1)
    return best
 
for line in sys.stdin:
    print(longest_unique(line.rstrip("\n")))

Type these three lines in the input:

abcabcbb
bbbbb
pwwkew

The output is:

3
1
3

Step through abcabcbb with the window in mind. At i = 0 the letter a has no earlier index, so last.get("a", -1) is -1, which is less than start, and nothing moves. The window is a, and best becomes 1. The letters b and c behave the same way, so after i = 2 the window is abc and best is 3. At i = 3 the letter is a again. Its last index is 0, which is at or after start (still 0), so start jumps to 1. The window is now bca, which is length 3, so best stays 3. At i = 4 the letter b was last seen at index 1, which is at or after start = 1. So start becomes 2, and the window is cab. This continues, and the window never grows past length 3.

The test last.get(c, -1) >= start is the key. Without it, start could move backward. Consider abba. At the last a (index 3), last["a"] is 0, but start is already 2 because the second b pushed it there. Moving start to 1 would wrongly bring back the second b into the window. The test stops start from moving backward.

Cost: O(n) time, because i moves forward once, and start only moves forward, so its total movement is at most n. Extra space is O(k), where k is the number of distinct characters, because the dict holds one entry for each character seen.

If you know the input is only lowercase English letters, a list is a little faster. Create last = [-1] * 26 and index it with ord(c) - ord("a"). The dict version is the one to write in an interview, because it does not depend on the alphabet.

The brute-force answer, and why the window beats it

The first answer most people write checks every substring. For each start, extend the end one letter at a time, and stop when a repeat appears. That is O(n squared) with a set, or O(n cubed) with a naive check of each substring. An interviewer may accept it as a first version, but you should move to the window next, and explain why the window is faster: each letter is added to the window once and removed at most once, so the work is linear.

Rotation check

The last problem is a short trick worth knowing. Is one string a rotation of another? For example, erbottlewat is a rotation of waterbottle, because cutting waterbottle after the t and moving the front part to the end gives erbottlewat. The trick is to notice that every rotation of s appears as a substring of s + s.

def is_rotation(a, b):
    return len(a) == len(b) and b in a + a
 
a = input()
b = input()
print("YES" if is_rotation(a, b) else "NO")

Type these two lines in the input:

waterbottle
erbottlewat

The output is:

YES

Why does a + a work? Write waterbottle twice: waterbottlewaterbottle. Any rotation is a window of length 11 inside that doubled string. The rotation erbottlewat starts at index 3 of the doubled string, at the e of water, and it runs for 11 characters, ending at the t at index 13. The in test finds it.

The length check is required. Without it, is_rotation("abab", "ab") would return true, because "ab" is found inside "abab" + "abab", even though the lengths differ. The check len(a) == len(b) is the first thing the function tests, and it is cheap. The in test is a substring search, which costs roughly O(n) time for these sizes, so the whole check runs in O(n) time with O(n) extra space for the doubled string.

What happens inside: the dict and the window

It helps to see what the sliding-window function keeps in memory, because the memory is small. The dict last holds one entry for each distinct character in the window's history, and its size depends on the alphabet, not on the length of the input. The function does not store the window itself. It stores only two numbers, start and i, and the window is the range between them. The characters inside the window stay in the original string, which is never copied.

When the program reads last[c], it does not scan the dict. Python computes the hash of c and goes straight to its slot. This is why the dict is fast. A list indexed by ord(c) is faster still, because it skips the hash, but it is less general.

Only one string is built, at the very end, with s[best_start:best_end] when the function must return the text itself. The loop does none of the copying that made the += version slow in the second lesson. Each step does a fixed amount of work, which is the reason the total time is O(n).

Explaining the window out loud

When you explain the sliding window in an interview, a short script keeps you on track. Say the steps in this order, and pause after each one so the interviewer can follow.

1. Restate the question: "I need the longest substring with no repeated letter, and I want its length."
2. Name the pattern: "This is a sliding window, because I want a range that grows and shrinks while keeping one property."
3. State the property: "Inside the window no letter appears twice."
4. Describe the two moves: "I move the right edge one step for each letter. If the new letter is already in the window, I move the left edge past its old position."
5. State the memory: "I need the last index of each letter, so I use a dict keyed by the character."
6. State the cost: "Each edge only moves forward, so the total work is O(n) time and O(k) extra space, where k is the number of distinct characters."
7. Name the edge cases: "An empty string gives 0, a string with no repeats gives its own length, and a string of one repeated letter gives 1."

Keep the explanation in your own words, and do not read it off a card. The order matters more than the exact words, because it shows the interviewer that you know what the code will do before you write it.

Interview view: the checklist

Interviewers rarely ask a bare question. They want to see that you can match the clue in the question to a pattern. The table below is the one to keep in mind.

When an interviewer gives you a problem, say the clue back before you write code: "The question asks for the longest substring with a property, so I will use a sliding window." Then state the cost, and mention the edge cases you will test: the empty string, a string with no repeats, a string where every letter repeats, and the character set. Naming the edge cases before you code shows that you think about correctness first.

Common mistakes

These are the mistakes that appear in real submissions to string problems.

Mistake 1: stopping the compression loop one step early. A loop written as while i < len(s) - 1 never writes the last run, because the last run has no different character after it to trigger the write. The fix is the loop structure above, where the inner loop always runs to the end of the run and the outer loop always moves past it.

The error you see is a wrong answer, not an exception, which makes it harder to notice. Test the compression on an input that ends in a run and still saves space, such as aaabb, and check that the output ends with b2. The encoding is a3b2, which is shorter than 5 characters, so it is returned.

Mistake 2: resetting the window to 0. This is the bug the debugging walkthrough below explains. Setting start to 0 when a repeat appears makes the window too big, and the answer is too large.

Mistake 3: start moving backward. Without the test last[c] >= start, a letter seen long before the window started can drag start back and include repeats. The check is short, and it is required.

Mistake 4: updating the best length too early. The best answer is the length of the window, i - start + 1, and it must be updated after the window is fixed for this index. Updating it before start moves gives a window that still contains the repeat.

Mistake 5: reading the wrong output. Some problems ask for the length, and others ask for the substring. Read the question twice. A program that prints 3 where the question wants abc fails the test even though its logic is sound.

Mistake 6: an index error with an empty string. s[0] on an empty string raises IndexError: string index out of range. Most of the functions in this lesson are safe on an empty string, because their loops never run. Test the empty case anyway, because a small change can break it.

Debugging walkthrough: the window that never shrinks

A teammate wrote the sliding window with a shortcut: when a repeat appears, reset the window to the beginning. Here is their version, and its output on the test cases from earlier.

def longest_unique_buggy(s):
    last = {}
    start = 0
    best = 0
    for i, c in enumerate(s):
        if last.get(c, -1) >= start:
            start = 0
        last[c] = i
        best = max(best, i - start + 1)
    return best
 
for text in ["abcabcbb", "bbbbb", "pwwkew", "abba"]:
    print(text, longest_unique_buggy(text))

The real output is:

abcabcbb 8
bbbbb 5
pwwkew 6
abba 4

These numbers are too big. A window of length 8 in abcabcbb must contain a repeat, because the whole string is only 8 letters and the letters repeat. The answer should be 3. Debug the output by asking "could this answer be right?". A window of length 5 in bbbbb is impossible, because the window can contain only one b. The impossible answers point to the window.

Now trace bbbbb. At i = 0 the window is b, and best is 1. At i = 1 the second b repeats, so start becomes 0 again. The window is bb, length 2, and best is 2. At i = 2 the repeat sets start to 0 again, so the window is bbb. The reset to 0 never shrinks the window, so the window grows to the full length, 5. That is the bug in one line: start = 0 should be start = last[c] + 1, which moves the left edge just past the old copy of the repeated letter.

Fix the line and run the four inputs again. The output becomes 3, 1, 3, and abba gives 2. The debugging method generalises: when an answer is impossible, find the variable that controls it, and trace that variable one step at a time on a short input. Here the variable was start, and the short input was bbbbb.

Variations and edge cases

Good string code handles the inputs the problem is quietly testing.

• An empty string. Compression returns the empty string. The first unique character returns -1. The longest substring without repeats returns 0. The rotation check of two empty strings returns true. Decide which answer you want and make sure the code returns it.
• A string with no repeats. The longest substring is the whole string. The window grows to the end and never shrinks.
• A string where every letter repeats. The first unique character is -1. The window keeps shrinking to length 1 when a repeat appears in a row like bbbbb.
• Uppercase and spaces. The dict handles every character, including uppercase letters and the space. A list of 26 counts does not, so use the dict when the problem allows any character. A list of 128 entries handles plain ASCII, but ord of a character above 127 raises IndexError for that list.
• Very long input. Build the output with a list and "".join, not with += in a loop, so a 100,000-character line stays fast. The second lesson explains why.
• Digits in the compression input. Run-length encoding is ambiguous when the text itself contains digits, because a2 could be a letter a with a count of 2, or the text a2. Ask whether the input can contain digits before you choose a format.

Practice

Try each exercise before you open the solution. The first three apply the lesson directly, and the last three ask for variations.

1. Decompress "a2b1c5a3" back to "aabcccccaaa" using decompress. Then predict the output of decompress("a10").
2. Check whether one string is a rotation of another, for example "waterbottle" and "erbottlewat". Use the a + a trick. Explain why the length check is needed with "ab" and "abab".
3. Trace longest_unique("pwwkew") and write down start and best after each step.
4. Write last_unique(s) that returns the index of the last unique character instead of the first. Explain why a single left-to-right scan cannot do this without storing indexes.
5. Write longest_unique_substring(s) that returns the substring itself, not its length. If two windows tie, return the earlier one.
6. Compress a string only when the compressed form is strictly shorter, and otherwise return the original. Test it on "aaa" and on "abc", and explain each answer in one sentence.
7. Write rotation_offset(a, b) that returns the number of positions you rotated a to get b, or -1 if b is not a rotation of a. Keep it O(n) time.
8. Write longest_two_distinct in your own words without looking at the lesson, and trace "eceba" with a table of start, i, the letters in the window and the best length.
9. Explain why longest_unique uses last.get(c, -1) >= start rather than only last.get(c, -1) != -1.
10. Explain, in three sentences or fewer, why the sliding window for the longest substring without repeats is O(n) even though a naive check of every substring needs two nested loops.

Show the answer

1. decompress("a2b1c5a3") returns aabcccccaaa. For a10 the count reads as 10, so the output is ten a characters, aaaaaaaaaa.
2. def is_rotation(a, b): return len(a) == len(b) and b in a + a. For "abab" and "ab" the doubled string "abab" + "abab" contains "ab", so without the length check the function would wrongly report true. The length check prevents that false answer.
3. The window steps: i = 0 p, start 0, best 1. i = 1 w, start 0, best 2. i = 2 w repeats at index 1, so start becomes 2, best stays 2. i = 3 k, start 2, best 2. i = 4 e, start 2, best 3. i = 5 w, last index 2, which is at or after start (2), so start becomes 3, and best stays 3. The answer is 3.
4. Count the letters as before, then scan from the right, returning the first index with count 1. A single left-to-right scan cannot decide whether a letter is unique, because a later copy may appear after it. Scanning right to left still needs the counts, which take a full pass first.
5. Track best_start and best_len as the window moves. Update both when i - start + 1 is strictly greater than best_len, which keeps the earlier window on a tie. Return s[best_start:best_start + best_len].
6. aaa encodes to a3, which has length 2, shorter than 3, so a3 is returned. abc encodes to a1b1c1, which has length 6, longer than 3, so abc is returned. The rule is to use the encoding only when it is shorter.
7. Check the lengths first. Then search a + a for b with find. The position where b starts inside a + a is the number of positions you rotated. The search is O(n) for the strings in this lesson. If find returns -1, return -1.
8. The table: i = 0 e, window e, start 0, best 1. i = 1 c, window ec, best 2. i = 2 e, window ece, best 3. i = 3 b makes three letters, so start moves to 1 and then to 2, window eb, best 3. i = 4 a makes three letters, so start moves to 3, window ba, best 3. The answer is 3.
9. The test last.get(c, -1) != -1 is true for any earlier copy of c, even one before start. Such a copy is outside the window, so it must be ignored. Without the >= start part, start could move backward, which breaks the window. The test >= start says "only a copy inside the window matters".
10. Each index is added to the window once, and start only moves forward, so the total number of moves of both edges is at most 2n. The moves of start use up positions that i has already passed, so no position is handled more than twice.

What you now know

• Run-length encoding writes each run as its letter and its count. A run is a block of equal neighbours, and the output keeps separate runs separate.
• Decompression reads each letter and then every digit after it as one number, so a12 means twelve a characters.
• The first unique character needs two passes: count first, then find the first index whose count is 1.
• The sliding window moves two indexes forward in one pass. The window grows on the right and shrinks on the left, and each index is visited once.
• The test last[c] >= start stops the left edge from moving backward.
• Rotation is a substring of the string doubled, and the length check is required.
• Name the clue in the question first, then name the pattern. Then state the cost and the edge cases.

The next lesson is the module assignment. It combines palindromes, anagrams, compression and the sliding window in one small program with a grading rubric.