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:
rightmoves 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
leftto just past the old copy. Everything after it stays. - A dictionary
lastremembers 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:rightis the index,chthe letter.right - left + 1is the window's length. (+ 1because both ends are included: from 1 to 3 is three letters.)- For the empty string the loop never runs and
beststays 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:
rightwalks the string once, and each step is a dictionary lookup and update, O(1) on average.leftonly 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 ofsand 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
a2b1a2for"aabaa": runs, not totals.- Twelve
as becomea12:str(count)writes as many digits as needed. "z": the looprange(1, 1)never runs, and the line after the loop writesz1.str(count)matters:"a" + 2is aTypeError(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
joinat 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
pairsmaps 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:
"(("saysTrue. Two boxes opened and never closed. At the end the stack still holds['(', '('], and we never looked."())"crashes withIndexError: pop from empty list. AnIndexErrormeans "there's no item at that position". After()the stack is empty, the second)has nothing to close, andpop()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, sonot stackisTruewhen it's empty. Andorstops at the first true part (short-circuit), sostack.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;
appendandpopat 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
- Longest substring without repeating characters: what's the optimal approach? A sliding window with a dictionary of each letter's last index.
rightmoves one step each time; if the letter was last seen inside the window (last[ch] >= left),leftjumps tolast[ch] + 1. The answer is the largestright - left + 1. O(n) time, O(k) space for k different letters. - 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). - 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.
- Why the
last[ch] >= leftcheck? The dictionary remembers letters that already left the window. Without the check, an old copy (like the firstain"abba") would moveleftbackwards, and the answer would be 3 instead of 2. - Why doesn't
Counterwork for string compression? It counts totals over the whole string; compression counts runs of equal neighbours."aabaa"must bea2b1a2, nota4b1. - 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. - Is there a library function for runs?
itertools.groupbygroups equal neighbours:"".join(ch + str(len(list(g))) for ch, g in groupby(s)). Write the loop first in an interview, then mention it. - Why can't you check brackets by counting? Counts ignore order:
")("and"([)]"have equal counts but are invalid. - 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"())"raisesIndexError: pop from empty list; andreturn not stackat the end, or"(("passes. O(n) time and space. - 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):rightmoves every step, and on a repeat inside the window,left = last[ch] + 1. The checklast[ch] >= leftstopsleftfrom jumping backwards ("abba"→ 2). - String compression: compression counts runs, not totals, so
Countergivesa4b1for"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.groupbygroups 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) andreturn not stackso 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.