SyntaxPilot
Courses/Python Coding Questions/Lesson 14
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 14 of 30

String questions IV

longest substring without repeating characters (sliding window)string compression (aabccc → a2b1c3)valid parentheses with a stack

These are the notes for Python Coding Questions, episode 14, the fourth round of string questions. Three questions that come up again and again in placement interviews: the longest substring without repeating characters, compressing a string ("aabccc" → "a2b1c3"), and checking that brackets are balanced. Each one needs one new idea. For the first it's a sliding window: two indexes that mark a stretch of the string, where you grow the right end and move the left end instead of starting again. For the second it's runs: compression counts letters that sit next to each other, not totals. For the third it's a stack: the last bracket opened must be the first one closed. Along the way you'll see a brute force timed for real (O(n³)), a loop that forgets its last group, and IndexError: pop from empty list.

Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real. Three things will differ on your machine: timings (they change from run to run and from computer to computer; each one shown here is a representative run), memory addresses like 0x7f6fd489b400, and tracebacks, which show the full path to your file; here it is shortened to main.py.

Q1: Longest substring without repeating characters

Real-life example: a college canteen serves one dish a day. Write each day's dish as a letter: dal, veg, dal, fish is d v d f. The students want the longest stretch of days in a row where no dish repeated. Here it's veg, dal, fish: 3 days. In code: the longest substring with no repeating character. A substring is a part of the string with no gaps: "vdf" is a substring of "dvdf", but "dvf" is not (it skips the second d).

Input Output The stretch
"abcabcbb" 3 "abc"
"bbbbb" 1 "b"
"dvdf" 3 "vdf"
"chaiwala" 5 "chaiw"
"abba" 2 "ab" or "ba"
"" (empty) 0 nothing

Ask the interviewer: do you want the length or the substring itself? Is it case-sensitive (is "A" the same as "a")? Can the string contain spaces, digits or any character? What should the empty string return?

Attempt 1: start again on a repeat

The obvious idea: walk the letters and grow the current stretch. When a letter repeats, throw the stretch away and start again. Keep the longest one seen.

def longest_unique(s):
    best = current = ""
    for ch in s:
        if ch in current:
            current = ""             # start again
        current += ch
        best = max(best, current, key=len)
    return len(best), best

for s in ["abcabcbb", "bbbbb", "dvdf", "chaiwala"]:
    print(s, longest_unique(s))

Output:

abcabcbb (3, 'abc')
bbbbb (1, 'b')
dvdf (2, 'dv')
chaiwala (5, 'chaiw')

Three right answers, and then dvdf gives 2 ('dv'). The answer is 3: 'vdf'. No error, just a wrong answer.

max(best, current, key=len) means: compare the two strings by their length (key=len) and return the longer one. On a tie, max keeps the first one, so best only changes when current is really longer. (Without key=len, max compares strings alphabetically: see the common mistakes table.)

Why it fails

A print in the loop shows what happened:

def longest_unique(s):
    best = current = ""
    for ch in s:
        if ch in current:
            print(f"{ch!r} repeats: throw away {current!r}")
            current = ""             # start again
        current += ch
        best = max(best, current, key=len)
        print(f"{ch!r} current={current!r} best={best!r}")
    return len(best), best

print(longest_unique("dvdf"))

Output:

'd' current='d' best='d'
'v' current='dv' best='dv'
'd' repeats: throw away 'dv'
'd' current='d' best='dv'
'f' current='df' best='dv'
(2, 'dv')

When the second d arrived, we threw away the whole stretch 'dv', including the v. But the v was still fine: only the old d had to go. The right move was to keep 'v' and continue with 'vd', then 'vdf'. Restarting throws away good letters.

Attempt 2: brute force, every substring

The safe way: check every substring. Brute force means trying every possibility. For every start i and every end j, take s[i:j]; if its set of letters (a set keeps each letter once) is as long as the substring, all its letters are different. Then try it on 1,040 letters and time it with time.perf_counter(), a clock for measuring short durations.

import time

def longest_unique(s):
    best = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            part = s[i:j]
            if len(set(part)) == len(part):     # all different?
                best = max(best, len(part))
    return best

print(longest_unique("dvdf"), longest_unique("chaiwala"))
s = "abcdefghijklmnopqrstuvwxyz" * 40          # 1,040 letters
start = time.perf_counter()
print(longest_unique(s), round(time.perf_counter() - start, 2), "seconds")

Output (the time differs on every run; three runs gave 1.02, 0.86 and 0.89 seconds):

3 5
26 1.01 seconds

Correct: 3 for dvdf, 5 for chaiwala, and 26 for the alphabet repeated (all 26 letters, then a repeat). But about a second for just a thousand letters.

Why it's slow: a string of n letters has n × (n + 1) / 2 substrings: about n²/2. Building each one's slice and set costs up to n steps. Together that's about n³ steps: O(n³) (read "order n cubed"). Double the input, and it's about eight times slower (2³ = 8). Watch it grow:

import time

def longest_unique(s):
    best = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            part = s[i:j]
            if len(set(part)) == len(part):     # all different?
                best = max(best, len(part))
    return best

for times in [10, 20, 40]:
    s = "abcdefghijklmnopqrstuvwxyz" * times
    start = time.perf_counter()
    longest_unique(s)
    print(len(s), "letters:", round(time.perf_counter() - start, 3), "seconds")
n = 1040
print(n * (n + 1) // 2, "substrings")

Output (a representative run):

260 letters: 0.026 seconds
520 letters: 0.158 seconds
1040 letters: 0.99 seconds
541320 substrings

Each doubling costs roughly six to eight times more (small inputs are a bit faster than the formula says). Over half a million substrings for 1,040 letters; for 100,000 letters this would take days.

The fix: a sliding window with a last-seen dictionary

Keep the good letters. Think of a window over the string, s[left : right + 1], that never contains a repeat:

  • right moves one step every time: the next day joins the window.
  • If the new letter is already inside the window, don't empty the window. Move left to just past the old copy. Everything after it stays.
  • A dictionary last remembers the last index where each letter was seen, so the jump is instant: left = last[ch] + 1.

This is the sliding window pattern, a kind of two pointers: two indexes, left and right, that only ever move forwards.

import time

def longest_unique(s):
    last = {}                  # letter -> index where we last saw it
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1          # jump past the old copy
        last[ch] = right
        best = max(best, right - left + 1)
    return best

for s in ["abcabcbb", "bbbbb", "dvdf", "chaiwala", "abba", ""]:
    print(repr(s), longest_unique(s))
s = "abcdefghijklmnopqrstuvwxyz" * 40
start = time.perf_counter()
print(longest_unique(s), round(time.perf_counter() - start, 4), "seconds")

Output (the time varies from run to run; here it was 0.0001 or 0.0002 seconds):

'abcabcbb' 3
'bbbbb' 1
'dvdf' 3
'chaiwala' 5
'abba' 2
'' 0
26 0.0001 seconds

Every test is right, dvdf is 3, and the same 1,040 letters take about a tenth of a millisecond instead of a second: roughly ten thousand times faster.

  • enumerate(s) gives (index, letter) pairs: right is the index, ch the letter.
  • right - left + 1 is the window's length. (+ 1 because both ends are included: from 1 to 3 is three letters.)
  • For the empty string the loop never runs and best stays 0.

Why last[ch] >= left? The abba case

last remembers every letter ever seen, even letters that have already left the window. Only a copy inside the window is a repeat. Here is the same function without the check:

def longest_unique_no_check(s):
    last = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last:                          # no ">= left" check
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
        print(f"right={right} ch={ch!r} left={left} window={s[left:right + 1]!r}")
    return best

print(longest_unique_no_check("abba"))

Output:

right=0 ch='a' left=0 window='a'
right=1 ch='b' left=0 window='ab'
right=2 ch='b' left=2 window='b'
right=3 ch='a' left=1 window='bba'
3

Wrong: 3, and the "window" 'bba' has a repeat. When the last a arrives, the old a is at index 0, but left is already at 2. That old a is outside the window. Without the check, left = 0 + 1 = 1: left jumps backwards and lets the second b back in. With last[ch] >= left, an old copy outside the window is ignored and left never moves back.

The window step by step

With a print at the end of each step of the correct version:

def longest_unique(s):
    last = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
        print(f"right={right} ch={ch!r} left={left} window={s[left:right + 1]!r} best={best} last={last}")
    return best

print(longest_unique("dvdf"))
print()
print(longest_unique("abba"))

Output:

right=0 ch='d' left=0 window='d' best=1 last={'d': 0}
right=1 ch='v' left=0 window='dv' best=2 last={'d': 0, 'v': 1}
right=2 ch='d' left=1 window='vd' best=2 last={'d': 2, 'v': 1}
right=3 ch='f' left=1 window='vdf' best=3 last={'d': 2, 'v': 1, 'f': 3}
3

right=0 ch='a' left=0 window='a' best=1 last={'a': 0}
right=1 ch='b' left=0 window='ab' best=2 last={'a': 0, 'b': 1}
right=2 ch='b' left=2 window='b' best=2 last={'a': 0, 'b': 2}
right=3 ch='a' left=2 window='ba' best=2 last={'a': 3, 'b': 2}
2

"dvdf":

right ch Seen inside the window? left Window best
0 d no 0 d 1
1 v no 0 dv 2
2 d yes, last['d'] = 0 >= 0 0 + 1 = 1 vd (the v is kept!) 2
3 f no 1 vdf 3

"abba":

right ch Seen inside the window? left Window best
0 a no 0 a 1
1 b no 0 ab 2
2 b yes, last['b'] = 1 >= 0 1 + 1 = 2 b 2
3 a last['a'] = 0, but 0 < left = 2: outside, ignore 2 ba 2
  • O(n) time: right walks the string once, and each step is a dictionary lookup and update, O(1) on average. left only ever jumps forwards.
  • O(k) space, where k is the number of different letters (one dictionary entry each). For lowercase English letters that's at most 26: effectively O(1).

Q2: String compression

Real-life example: a shopkeeper doesn't write samosa, samosa, samosa on his list. He writes samosa ×3. So "aabccc" becomes "a2b1c3": each letter, followed by how many times it repeats in a row. That's run-length encoding: a run is a group of the same letter sitting next to each other, and each run is written as the letter and its length. Notice in a row: if the order goes chai, chai, bun, chai, chai, the list says chai ×2, bun ×1, chai ×2, not chai ×4.

Input Output
"aabccc" "a2b1c3"
"aabaa" "a2b1a2" (runs, not totals)
"aaaaaaaaaaaab" "a12b1" (a count can have two digits)
"abc" "a1b1c1" (longer than the input!)
"" ""
"z" "z1"

Ask the interviewer: are counts of 1 written (b1) or left out (b)? If the compressed string is not shorter, should I return the original? Is it case-sensitive? Can the input contain digits? (If it can, "a2" would compress to "a121", which can't be undone.)

Attempt 1: a Counter

Counter (from collections) counts each letter. Join each letter with its count:

from collections import Counter

def compress(s):
    return "".join(ch + str(n) for ch, n in Counter(s).items())

print(compress("aabccc"))
print(compress("aabaa"))

Output:

a2b1c3
a4b1

a2b1c3: correct. But "aabaa" gives a4b1. It should be a2b1a2.

Why it fails: a Counter counts totals over the whole string. It doesn't know which letters were neighbours:

from collections import Counter

print(Counter("aabaa"))
print(Counter("aabccc"))

Output:

Counter({'a': 4, 'b': 1})
Counter({'c': 3, 'a': 2, 'b': 1})

Both a runs are added into one total of 4. "aabccc" only worked by luck: each letter there has exactly one run. Compression needs runs.

Attempt 2: a loop over the runs

Walk the string and compare each letter with the one before it. Same letter: the run grows. Different: the run before it just ended, so write it down and start a new count.

def compress(s):
    out = []
    count = 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            count += 1
        else:
            out.append(s[i - 1] + str(count))   # a run just ended
            count = 1
    return "".join(out)

print(compress("aabccc"))
print(compress("aabaa"))

Output:

a2b1
a2b1

Where's c3? And "aabaa" lost its last a2.

Why: the last run never closes

def compress(s):
    out = []
    count = 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            count += 1
        else:
            out.append(s[i - 1] + str(count))
            count = 1
        print(f"i={i} s[i-1]={s[i - 1]!r} s[i]={s[i]!r} count={count} out={out}")
    print("loop over: count =", count, "for", repr(s[-1]), "is never added")
    return "".join(out)

print(compress("aabccc"))

Output:

i=1 s[i-1]='a' s[i]='a' count=2 out=[]
i=2 s[i-1]='a' s[i]='b' count=1 out=['a2']
i=3 s[i-1]='b' s[i]='c' count=1 out=['a2', 'b1']
i=4 s[i-1]='c' s[i]='c' count=2 out=['a2', 'b1']
i=5 s[i-1]='c' s[i]='c' count=3 out=['a2', 'b1']
loop over: count = 3 for 'c' is never added
a2b1

A run is written down only when a different letter comes after it. Run 1 (aa) closes when b arrives; run 2 (b) closes when c arrives. Run 3 (ccc) has no letter after it: the loop ends, count is 3, and it's lost. This is a classic off-by-one bug: the code is right for every step but one, here the last.

The fix: close the last run after the loop

  • After the loop: out.append(s[-1] + str(count)): the last letter of s and its count.
  • But an empty string has no last letter, and s[-1] would crash. So return "" first.

Here is the crash, if you forget the empty check:

def compress(s):
    out = []
    count = 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            count += 1
        else:
            out.append(s[i - 1] + str(count))
            count = 1
    out.append(s[-1] + str(count))          # the last run, but no empty check
    return "".join(out)

print(compress("aabccc"))
print(compress(""))

Output:

a2b1c3
Traceback (most recent call last):
  File "main.py", line 14, in <module>
    print(compress(""))
          ~~~~~~~~^^^^
  File "main.py", line 10, in compress
    out.append(s[-1] + str(count))          # the last run, but no empty check
               ~^^^^
IndexError: string index out of range

The full fix, with both:

def compress(s):
    if not s:
        return ""                           # no runs at all
    out = []
    count = 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            count += 1
        else:
            out.append(s[i - 1] + str(count))
            count = 1
    out.append(s[-1] + str(count))          # the last run
    return "".join(out)

for s in ["aabccc", "aabaa", "aaaaaaaaaaaab", "abc", "", "z"]:
    print(repr(s), "->", repr(compress(s)))
print(min("abc", compress("abc"), key=len))   # keep the shorter one

Output:

'aabccc' -> 'a2b1c3'
'aabaa' -> 'a2b1a2'
'aaaaaaaaaaaab' -> 'a12b1'
'abc' -> 'a1b1c1'
'' -> ''
'z' -> 'z1'
abc
  • a2b1a2 for "aabaa": runs, not totals.
  • Twelve as become a12: str(count) writes as many digits as needed.
  • "z": the loop range(1, 1) never runs, and the line after the loop writes z1.
  • str(count) matters: "a" + 2 is a TypeError (see the common mistakes table).

The follow-up: keep the shorter one

"abc" becomes "a1b1c1", which is longer. Many versions of the question say: return the compressed string only if it's shorter. min(a, b, key=len) returns the shorter of the two; on a tie it returns the first one, so put the original first:

def compress(s):
    if not s:
        return ""
    out = []
    count = 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            count += 1
        else:
            out.append(s[i - 1] + str(count))
            count = 1
    out.append(s[-1] + str(count))
    return "".join(out)

def shortest(s):
    c = compress(s)
    return min(s, c, key=len)

for s in ["aabccc", "abc", "aaaaab", "aabb"]:
    print(repr(s), "->", repr(compress(s)), "shorter:", repr(shortest(s)))

Output:

'aabccc' -> 'a2b1c3' shorter: 'aabccc'
'abc' -> 'a1b1c1' shorter: 'abc'
'aaaaab' -> 'a5b1' shorter: 'a5b1'
'aabb' -> 'a2b2' shorter: 'aabb'

"aabccc" and "a2b1c3" are both 6 long, so the tie keeps the original. Only "aaaaab" really gets shorter.

The ready-made tool: itertools.groupby

groupby (from the itertools module) groups neighbours that are equal: exactly a run.

from itertools import groupby

print([(ch, len(list(run))) for ch, run in groupby("aabaa")])
print("".join(ch + str(len(list(run))) for ch, run in groupby("aabccc")))

Output:

[('a', 2), ('b', 1), ('a', 2)]
a2b1c3

groupby("aabaa") gives three groups, a, b, a: runs. (That's the same trap from episode 10, seen from the other side: groupby only groups equal neighbours, so to group by totals you must sort first.) Each group is a pair: the letter, and a lazy iterator over that run's letters. len() doesn't work on an iterator, so we turn it into a list first:

from itertools import groupby

for ch, run in groupby("aabaa"):
    print(repr(ch), run, list(run))
print(list(groupby("")))

Output (the addresses change on every run):

'a' <itertools._grouper object at 0x7f6fd489b400> ['a', 'a']
'b' <itertools._grouper object at 0x7f6fd489b430> ['b']
'a' <itertools._grouper object at 0x7f6fd489b400> ['a', 'a']
[]

The empty string gives no groups at all, so the groupby one-liner returns "" with no special check.

In an interview, write the loop first. It shows you understand runs and the last group. Then mention groupby.

  • O(n) time: one pass over the string, and one join at the end.
  • O(n) space for the output list and the new string (it's the answer, so it has to exist).

Q3: Valid parentheses

Real-life example: nested tiffin boxes. You open the big box, then the small box inside it. To pack up, you close the small one first, then the big one: last opened, first closed. Closing the big lid while the small box is still open doesn't work. Brackets are the same: round (), square [] and curly {} brackets must close in the right order.

Input Output
"(a[b]{c})" True
"{[()()]}" True
"([)]" False (closed in the wrong order)
"((" False (never closed)
"())" False (a closer with nothing to close)
")(" False (closer before its opener)
"" True
"print(x[0])" True (other characters are ignored)

Ask the interviewer: which bracket types? Are other characters allowed, and should they be ignored? Is the empty string valid?

Attempt 1: count the brackets

The first idea most people have: valid if the number of ( equals the number of ), and the same for [ and ].

def is_valid(s):
    return (s.count("(") == s.count(")") and
            s.count("[") == s.count("]"))

for s in ["(chai)", "(()())", ")(", "([)]"]:
    print(s, is_valid(s))

Output:

(chai) True
(()()) True
)( True
([)] True

The first two are right. But )( is True, and ([)] is True.

Why it fails: counting checks how many, not in what order. A closing bracket before its opener, or lids closed in the wrong order, have the same counts as a valid string.

Attempt 2: a stack

We need to remember which box was opened last. That's a stack: a pile where the last item in is the first item out (LIFO, "last in, first out"), like a pile of plates. A Python list works as one:

  • Push (put on top): stack.append(ch), for every opening bracket.
  • Pop (take off the top): stack.pop() removes and returns the last item. For every closing bracket, the popped opener must be the matching one.
  • A dictionary pairs maps each closer to its opener, so one comparison checks any bracket type.
def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)               # an opening bracket waits
        elif ch in pairs:
            if stack.pop() != pairs[ch]:   # must close the latest one
                return False
    return True

for s in ["(a[b]{c})", "([)]", "(("]:
    print(s, is_valid(s))
print(is_valid("())"))

Output:

(a[b]{c}) True
([)] False
(( True
Traceback (most recent call last):
  File "main.py", line 14, in <module>
    print(is_valid("())"))
          ~~~~~~~~^^^^^^^
  File "main.py", line 8, in is_valid
    if stack.pop() != pairs[ch]:   # must close the latest one
       ~~~~~~~~~^^
IndexError: pop from empty list

Better: nested brackets with letters inside are True, and the crossed ([)] is False now. But two holes:

  1. "((" says True. Two boxes opened and never closed. At the end the stack still holds ['(', '('], and we never looked.
  2. "())" crashes with IndexError: pop from empty list. An IndexError means "there's no item at that position". After () the stack is empty, the second ) has nothing to close, and pop() on an empty list raises.

The fix: guard the pop, and return not stack

  • Before popping: if the stack is empty, return False. if not stack or ...: an empty list is falsy, so not stack is True when it's empty. And or stops at the first true part (short-circuit), so stack.pop() never runs on an empty stack.
  • At the end: valid only if nothing is left open: return not stack.
def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False               # nothing to close, or wrong type
    return not stack                       # anything still open?

for s in ["(a[b]{c})", "{[()()]}", "([)]", "((", "())", ")(",
          "", "print(x[0])"]:
    print(repr(s), is_valid(s))

Output:

'(a[b]{c})' True
'{[()()]}' True
'([)]' False
'((' False
'())' False
')(' False
'' True
'print(x[0])' True

Every case is right. The empty string is valid (nothing opened, nothing left), and a real line of code, print(x[0]), is valid: letters are neither openers nor closers, so they're skipped.

What not stack gives for a leftover stack and an empty one:

stack = ["(", "("]
print(not stack, bool(stack), not [])

Output:

False True True

The stack step by step

With a print at every push and pop:

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
            print(f"{ch!r} push     stack={stack}")
        elif ch in pairs:
            if not stack:
                print(f"{ch!r} nothing to close")
                return False
            top = stack.pop()
            print(f"{ch!r} pop {top!r}  stack={stack}", "match" if top == pairs[ch] else "WRONG BOX")
            if top != pairs[ch]:
                return False
    print("end: stack =", stack)
    return not stack

print(is_valid("([)]"))
print()
print(is_valid("{[()()]}"))

Output:

'(' push     stack=['(']
'[' push     stack=['(', '[']
')' pop '['  stack=['('] WRONG BOX
False

'{' push     stack=['{']
'[' push     stack=['{', '[']
'(' push     stack=['{', '[', '(']
')' pop '('  stack=['{', '['] match
'(' push     stack=['{', '[', '(']
')' pop '('  stack=['{', '['] match
']' pop '['  stack=['{'] match
'}' pop '{'  stack=[] match
end: stack = []
True

"([)]":

ch Action Stack after
( push ['(']
[ push ['(', '[']
) pop gives [, but ) needs (: wrong box, return False ['(']

"{[()()]}":

ch Action Stack after
{ push ['{']
[ push ['{', '[']
( push ['{', '[', '(']
) pop (: match ['{', '[']
( push ['{', '[', '(']
) pop (: match ['{', '[']
] pop [: match ['{']
} pop {: match []
end stack empty: return not stack gives True []
  • O(n) time: one pass; append and pop at the end of a list are O(1).
  • O(n) space: the stack can hold up to n openers (for "((((((").

This same stack is how your editor highlights matching brackets and how the Python parser spots SyntaxError: '(' was never closed.

Common mistakes (and what you really see)

Mistake What you see Why Fix
current = "" on a repeat dvdf (2, 'dv'): should be 3 throws away good letters left = last[ch] + 1
every substring + set() 26 1.01 seconds for 1,040 letters O(n³) a sliding window, O(n)
if ch in last: without last[ch] >= left "abba" → 3 an old copy outside the window moves left backwards if ch in last and last[ch] >= left:
max(best, current) without key=len max("abc", "b") → b strings compare alphabetically max(best, current, key=len)
Counter(s) to compress "aabaa" → a4b1 totals, not runs compare with the previous letter
append only when the letter changes "aabccc" → a2b1 the last run never closes append once more after the loop
s[-1] with no empty check IndexError: string index out of range "" has no last letter if not s: return "" first
"a" + count TypeError: can only concatenate str (not "int") to str a number isn't a string "a" + str(count)
count ( and ) only ")(" → True counts ignore order a stack
stack.pop() with no check IndexError: pop from empty list nothing to close if not stack or stack.pop() != ...
stack[-1] to peek at an empty stack IndexError: list index out of range no top item check if stack: first
pairs[ch] for an opener KeyError: '(' pairs only has closers as keys check ch in pairs first
return True at the end "((" → True openers left over return not stack

Your turn: decompress (solution)

Undo the compression: a letter, then its count. "a2b1c3" → "aabccc", and "a12b1" → "aaaaaaaaaaaab". The catch: a count can have more than one digit.

Solution

The trap first. Reading "one letter, then one digit" works for a2b1c3, but not for a12b1:

def decompress(s):
    out = []
    for i in range(0, len(s), 2):          # a letter, then ONE digit
        out.append(s[i] * int(s[i + 1]))
    return "".join(out)

print(decompress("a2b1c3"))
print(decompress("a12b1"))

Output:

aabccc
Traceback (most recent call last):
  File "main.py", line 8, in <module>
    print(decompress("a12b1"))
          ~~~~~~~~~~^^^^^^^^^
  File "main.py", line 4, in decompress
    out.append(s[i] * int(s[i + 1]))
                      ~~~^^^^^^^^^^
ValueError: invalid literal for int() with base 10: 'b'

The pairs become a1, then 2b: int("b") is not a number, so a ValueError (the right type, but a value that can't be used). A worse version would silently give the wrong answer.

The fix: after each letter, read all the digits that follow (ch.isdigit() is True for 0 to 9), then repeat the letter that many times. ch * n repeats a string n times: "a" * 3 is "aaa".

def decompress(s):
    out = []
    i = 0
    while i < len(s):
        ch = s[i]                          # the letter
        i += 1
        j = i
        while j < len(s) and s[j].isdigit():
            j += 1                         # read ALL the digits
        out.append(ch * int(s[i:j]))
        i = j
    return "".join(out)

for s in ["a2b1c3", "a12b1", "a2b1a2", "z1", ""]:
    print(repr(s), "->", repr(decompress(s)))

Output:

'a2b1c3' -> 'aabccc'
'a12b1' -> 'aaaaaaaaaaaab'
'a2b1a2' -> 'aabaa'
'z1' -> 'z'
'' -> ''

Step by step for "a12b1":

def decompress(s):
    out = []
    i = 0
    while i < len(s):
        ch = s[i]
        i += 1
        j = i
        while j < len(s) and s[j].isdigit():
            j += 1
        print(f"letter {ch!r}, digits s[{i}:{j}] = {s[i:j]!r}")
        out.append(ch * int(s[i:j]))
        i = j
    return "".join(out)

print(decompress("a12b1"))

Output:

letter 'a', digits s[1:3] = '12'
letter 'b', digits s[4:5] = '1'
aaaaaaaaaaaab

j walks past both digits 1 and 2, so the slice s[1:3] is '12', and int('12') is twelve. i = j continues from the next letter. The inner while checks j < len(s) first, so it never reads past the end. O(m) time, where m is the length of the output (every letter is written once), and O(m) space.

Practice questions (with solutions)

1. Decompress with a regular expression, and check the round trip. Write decompress in one line, and check that decompress(compress(s)) == s for every test.

Solution

The re module finds patterns in text. re.findall(r"(\D)(\d+)", s) finds every "one non-digit (\D), then one or more digits (\d+)" and returns the two parts as a pair. \d+ takes all the digits, so a12 is one match.

import re

def compress(s):
    if not s:
        return ""
    out = []
    count = 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            count += 1
        else:
            out.append(s[i - 1] + str(count))
            count = 1
    out.append(s[-1] + str(count))
    return "".join(out)

def decompress(s):
    return "".join(ch * int(n) for ch, n in re.findall(r"(\D)(\d+)", s))

print(re.findall(r"(\D)(\d+)", "a12b1"))
for s in ["aabccc", "aabaa", "aaaaaaaaaaaab", "z", ""]:
    c = compress(s)
    print(repr(s), "->", repr(c), "->", repr(decompress(c)), decompress(c) == s)

Output:

[('a', '12'), ('b', '1')]
'aabccc' -> 'a2b1c3' -> 'aabccc' True
'aabaa' -> 'a2b1a2' -> 'aabaa' True
'aaaaaaaaaaaab' -> 'a12b1' -> 'aaaaaaaaaaaab' True
'z' -> 'z1' -> 'z' True
'' -> '' -> '' True

A round trip (compress, then decompress, and compare with the start) is a quick way to test both functions at once. It only works if the input has no digits: ask the interviewer. O(m) time, where m is the output length.

2. Longest substring with at most 2 different letters. "eceba" → 3 ("ece"), "ccaabbb" → 5 ("aabbb").

Solution

The same sliding window, with a different rule: the window may hold at most two different letters. Keep a dictionary count of how many of each letter are in the window. right adds a letter; while there are more than two kinds, remove letters from the left one at a time (deleting a letter from the dictionary when its count reaches 0).

def longest_two_kinds(s):
    count = {}                         # letter -> how many in the window
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while len(count) > 2:          # too many kinds: shrink from the left
            out = s[left]
            count[out] -= 1
            if count[out] == 0:
                del count[out]
            left += 1
        best = max(best, right - left + 1)
    return best

for s in ["eceba", "ccaabbb", "aaaa", "abc", "chaiwala", ""]:
    print(repr(s), longest_two_kinds(s))

Output:

'eceba' 3
'ccaabbb' 5
'aaaa' 4
'abc' 2
'chaiwala' 3
'' 0

count.get(ch, 0) gives 0 for a letter not in the dictionary yet. Here left can't jump (we don't know how far), so it walks; but each letter enters the window once and leaves at most once, so the total work is still O(n) time. O(1) space: the dictionary never holds more than three letters. Replace 2 with k for the general "at most k different letters" question.

3. Minimum brackets to add to make s valid. Only round brackets. "())" → 1, "(((" → 3, "()))((" → 4.

Solution

With one bracket type, the stack only ever holds (, so a counter of open brackets is enough. A ) with an opener waiting closes it. A ) with nothing waiting needs a ( added before it. At the end, every opener still waiting needs a ) added.

def min_add(s):
    open_ = 0      # openers still waiting for a closer
    added = 0      # openers we had to add for a lonely closer
    for ch in s:
        if ch == "(":
            open_ += 1
        elif ch == ")":
            if open_ > 0:
                open_ -= 1
            else:
                added += 1
    return added + open_       # plus a closer for every opener left over

for s in ["())", "(((", "()", "()))((", ")(", ""]:
    print(repr(s), min_add(s))

Output:

'())' 1
'(((' 3
'()' 0
'()))((' 4
')(' 2
'' 0

These are exactly the two holes of Attempt 2 in Q3: added counts the "pop from an empty stack" cases, and open_ at the end counts the leftovers. (open_ has an underscore because open is the name of a built-in function.) O(n) time, O(1) space.

4. Longest valid parentheses run. The longest substring of round brackets that is valid. ")()())" → 4 ("()()"), "(()" → 2.

Solution

A stack of indexes. The bottom of the stack is always the index just before the current valid run (it starts as -1). Push the index of every (. For a ), pop: if the stack is now empty, this ) can't be matched, and it becomes the new base; otherwise the valid run ends here and its length is i - stack[-1].

def longest_valid(s):
    stack = [-1]           # index just BEFORE the current valid run
    best = 0
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)        # this ")" can't be matched: new base
            else:
                best = max(best, i - stack[-1])
    return best

for s in ["(()", ")()())", "()(())", "())()", "((", ""]:
    print(repr(s), longest_valid(s))

Output:

'(()' 2
')()())' 4
'()(())' 6
'())()' 2
'((' 0
'' 0

Step by step for ")()())":

def longest_valid(s):
    stack = [-1]
    best = 0
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
        print(f"i={i} {ch!r} stack={stack} best={best}")
    return best

print(longest_valid(")()())"))

Output:

i=0 ')' stack=[0] best=0
i=1 '(' stack=[0, 1] best=0
i=2 ')' stack=[0] best=2
i=3 '(' stack=[0, 3] best=2
i=4 ')' stack=[0] best=4
i=5 ')' stack=[5] best=4
4

The first ) pops the -1 and becomes the base (index 0). At i = 4 the run since the base is indexes 1 to 4: 4 - 0 = 4. The last ) empties the stack again and becomes a new base. The stack is never popped while empty, because the base is always there. O(n) time, O(n) space.

5. Return the longest unique substring itself, not just its length. "dvdf" → "vdf".

Solution

The Q1 sliding window, plus one more number: start, where the best window began. Update it only when the window is strictly longer than the best so far, so the first one wins a tie.

def longest_unique_text(s):
    last = {}
    left = best = start = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        if right - left + 1 > best:
            best = right - left + 1
            start = left               # remember where the best window began
    return s[start:start + best]

for s in ["abcabcbb", "bbbbb", "dvdf", "chaiwala", "abba", ""]:
    print(repr(s), repr(longest_unique_text(s)))

Output:

'abcabcbb' 'abc'
'bbbbb' 'b'
'dvdf' 'vdf'
'chaiwala' 'chaiw'
'abba' 'ab'
'' ''

Slicing once at the end (instead of building the substring at every step) keeps it O(n) time.

6. Maximum nesting depth. How deep do the round brackets go? "(1+(2*3)+((8)/4))+1" → 3.

Solution

Like Practice 3, one bracket type needs only a counter: the depth is how many boxes are open right now, which is the stack's size. Track the largest it ever gets.

def max_depth(s):
    depth = best = 0
    for ch in s:
        if ch == "(":
            depth += 1
            best = max(best, depth)
        elif ch == ")":
            depth -= 1
    return best

for s in ["(1+(2*3)+((8)/4))+1", "(a)(b)", "print(x)", "no brackets"]:
    print(repr(s), max_depth(s))

Output:

'(1+(2*3)+((8)/4))+1' 3
'(a)(b)' 1
'print(x)' 1
'no brackets' 0

In ((8)/4) inside the outer brackets, the 8 sits three boxes deep. This assumes the string is already valid (check with Q3 first). O(n) time, O(1) space.

Quick quiz

What does this print?

stack = []
for ch in "([{":
    stack.append(ch)
print(stack.pop(), stack.pop(), stack)

(A) ( [ ['{'] (B) { [ ['('] (C) { ( ['['] (D) [ { ['(']

Answer

(B). append adds to the end of the list, and pop() removes from the end: last in, first out. The pushes leave ['(', '[', '{']. The first pop() returns '{', the second '[', and ['('] is left. (The arguments of print are evaluated left to right, so both pops happen before stack is printed.)

{ [ ['(']

Interview questions

  1. Longest substring without repeating characters: what's the optimal approach? A sliding window with a dictionary of each letter's last index. right moves one step each time; if the letter was last seen inside the window (last[ch] >= left), left jumps to last[ch] + 1. The answer is the largest right - left + 1. O(n) time, O(k) space for k different letters.
  2. Why is "start again on a repeat" wrong? It throws away the letters after the old copy, which were still fine. "dvdf" gives 2 (dv) instead of 3 (vdf).
  3. What's the brute-force complexity, and why? O(n³): about n²/2 substrings, and checking each one (slicing and building a set) costs up to n. Doubling the input makes it about eight times slower.
  4. Why the last[ch] >= left check? The dictionary remembers letters that already left the window. Without the check, an old copy (like the first a in "abba") would move left backwards, and the answer would be 3 instead of 2.
  5. Why doesn't Counter work for string compression? It counts totals over the whole string; compression counts runs of equal neighbours. "aabaa" must be a2b1a2, not a4b1.
  6. What's the classic bug in the compression loop? The last run is written only when a different letter follows it, and none does, so it's lost: an off-by-one bug. Append s[-1] + str(count) after the loop, and return "" first for an empty string.
  7. Is there a library function for runs? itertools.groupby groups equal neighbours: "".join(ch + str(len(list(g))) for ch, g in groupby(s)). Write the loop first in an interview, then mention it.
  8. Why can't you check brackets by counting? Counts ignore order: ")(" and "([)]" have equal counts but are invalid.
  9. How does the stack solution work, and what are its two edge cases? Push every opener; for every closer, pop and check it's the matching opener. Guard the pop (if not stack), or "())" raises IndexError: pop from empty list; and return not stack at the end, or "((" passes. O(n) time and space.
  10. Why a dictionary of closers to openers? One lookup gives the opener any closer needs, so the same line handles (), [] and {}, and adding a new bracket type is one more entry.

Glossary

Term Meaning Example
Substring A part of a string with no gaps "vdf" in "dvdf"; "dvf" is not one
Repeating character A character that appears more than once d in "dvdf"
Brute force Try every possibility check every substring
O(n), O(n²), O(n³), O(1) Time or space that grows like n, n × n, n × n × n, or not at all one pass; all substrings; check each substring; a dictionary lookup
O(k) Grows with k, the number of different letters the last dictionary
time.perf_counter() A clock for timing short pieces of code time.perf_counter() - start
Sliding window A stretch s[left : right + 1] whose ends only move forwards grow right, jump left
Two pointers Two indexes moving through the data left and right
Window length right - left + 1 (both ends included) left = 1, right = 3 → 3
Last-seen dictionary Maps each letter to the index where it was last seen last = {'d': 2, 'v': 1}
Dictionary (dict) Maps keys to values with O(1) average lookup pairs = {")": "("}
dict.get(k, 0) The value for k, or 0 if k isn't there count.get(ch, 0) + 1
enumerate Gives (index, value) pairs while looping for right, ch in enumerate(s)
Set A collection of unique items len(set("dvd")) → 2
max(..., key=len) / min(..., key=len) The longest / shortest; on a tie, the first one min("abc", "a1b1c1", key=len) → 'abc'
Run A group of the same character sitting next to each other "aabaa" has runs aa, b, aa
Run-length encoding Writing each run as its character and its length "aabccc" → "a2b1c3"
String compression Making a string shorter; here, run-length encoding "aaaaab" → "a5b1"
Counter A dict that counts totals; missing keys give 0 Counter("aabaa") → {'a': 4, 'b': 1}
Off-by-one bug Code that is right for every step but one, often the first or last the forgotten last run
str(n) Turns a number into text "a" + str(12) → 'a12'
str.join Glues strings from an iterable together "".join(["a2", "b1"]) → 'a2b1'
itertools.groupby Groups neighbours that are equal, giving (key, group) pairs groupby("aabaa") → 3 groups
Iterator Hands out items one at a time; len() doesn't work on it the group from groupby
Round trip Encode, decode, and check you got the start back decompress(compress(s)) == s
isdigit() True for the digits 0 to 9 "7".isdigit() → True
ch * n A string repeated n times "a" * 3 → 'aaa'
re.findall Finds every match of a pattern re.findall(r"(\D)(\d+)", "a12b1")
Stack A pile where the last item in is the first out a Python list
LIFO Last in, first out the last box opened is closed first
Push Put an item on top of the stack stack.append(ch)
Pop Remove and return the top item stack.pop()
Peek Look at the top item without removing it stack[-1]
Opener / closer An opening / closing bracket (, [, { / ), ], }
Nesting depth How many brackets are open at once ((8)) has depth 2
Truthy / falsy Values that count as True / False in an if [] is falsy, ['('] truthy
not stack True when the list is empty return not stack
Short-circuit or / and stop as soon as the answer is known not stack or stack.pop() never pops an empty list
IndexError No item at that position pop from empty list, string index out of range
KeyError A dictionary has no such key pairs["("] → KeyError: '('
TypeError An operation the types don't support "a" + 2
ValueError The right type, but a value that can't be used int("b")
Edge case An unusual input that often breaks code "", "z", "abba", "(("

Summary

  • Longest substring without repeats: "start again on a repeat" throws away good letters ("dvdf" → 2 instead of 3). Checking every substring is right but O(n³): about a second for 1,040 letters. A sliding window with a last-seen dictionary is O(n): right moves every step, and on a repeat inside the window, left = last[ch] + 1. The check last[ch] >= left stops left from jumping backwards ("abba" → 2).
  • String compression: compression counts runs, not totals, so Counter gives a4b1 for "aabaa". Compare each letter with the one before; the last run has no next letter, so append it after the loop, and handle "" first. min(s, compressed, key=len) keeps the shorter one; itertools.groupby groups equal neighbours. O(n).
  • Valid parentheses: counting ignores order (")(" → True). A stack does it: push openers, and every closer must pop its matching opener. Guard the pop (IndexError: pop from empty list) and return not stack so leftover openers fail. O(n) time and space.

Next episode: String questions V: building strings in a loop with += against "".join, timed for real; a caesar cipher with ord and chr; and checking whether one string is a rotation of another.