1Understand
The idea
Walk the string once, keeping just enough state for the task: the current number being read, the current run, a stack of what is open. Build the result in a list and join it at the end. For digit-by-digit arithmetic, process from the least significant end and carry over.
Intuition
Walk the string once, keeping just enough state for the task: the current number being parsed, the current run length, a stack of open frames. Build the output in a list and join at the end.
Digit-by-digit arithmetic processes from the least significant end with a carry. Parsing problems fail on edge cases (signs, leading zeros, overflow) more often than on the main loop.
If nesting appears, you almost certainly want a stack alongside the scan.
What you will be able to do
- Walk a string with an explicit index
- Carry digits right to left
- Design an unambiguous encoding
When to use it
- Convert between a string and another representation
- Numbers too large for built-in types, given as strings
- Encode a list so it can be decoded exactly
2See it
Walkthrough
Parse with two indices
s = "42", accumulate digits into an integer.
1 / 5
num = 0. Read sign/spaces first in fuller parsers; here plain digits.
Live template
Line 1 active
Complexity: time O(n), space O(n)
One pass O(n + m) time and space for the output. Regex-heavy parsing can be clearer but harder to control edge cases in interviews. Prefer explicit index walks for digit/run problems.
Read the walkthrough as text
Add strings. num1 = "456", num2 = "77".
- i, j at last indices; carry = 0; out = [].
- Add
6+7+0 = 13→ write3, carry1. - Add
5+7+1 = 13→ write3, carry1. - Add
4+0+1 = 5→ write5. Join reversed →"533".
In code:
while i >= 0 or j >= 0 or carry:s = carryif i >= 0: s += int(num1[i]); i -= 1if j >= 0: s += int(num2[j]); j -= 1out.append(str(s % 10)); carry = s // 10return ''.join(reversed(out))
3Recognise it
Kinds of problems (8)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Encode / decode with length prefixes
Example. Serialize list of strings with unambiguous delimiter.
How. Store len#str per piece so payload may contain any char.
Arithmetic on digit strings (add, multiply)
Example. Add two non-negative integers given as strings.
How. Reverse or index from right; digit sums with carry.
Parse and convert (Roman numerals, string to integer)
Example. Convert Roman numeral to integer.
How. Scan left to right; subtract value if next symbol is larger.
Run-length compression
Example. Compress consecutive repeats (count + char).
How. Walk and group runs; emit len+char when run ends.
Character-to-word bijection (isomorphic strings, word pattern)
Example. s and t isomorphic; pattern matches words.
How. Two dicts map char→word and word→char; reject on conflict.
Common prefix of several strings
Example. Longest common prefix in string list.
How. Vertical scan until mismatch on column i across all strings.
Simulate writing in a pattern (zigzag)
Example. Zigzag conversion on rows.
How. Track row and direction; append char to row buckets then join.
Line layout (word wrap, text justification)
Example. Format text to width w with justified lines.
How. Greedy pack words per line; pad spaces evenly except last line rules.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Delimiter collision
Why it happens. Comma or pipe separators are quick to implement.
How it fails. Encode ["a,b","c"] with comma delimiter, decode splits payload wrong.
Fix. Length-prefix encoding: `f"{len(str)}#{str}"`.
Carry lost
Why it happens. Loop stops when one string ends.
How it fails. Add "99" + "1" left-to-right without final carry, answer "90" instead of "100".
Fix. Process from right; after loop if carry: append carry.
Sign or leading zeros
Why it happens. Leading zeros look harmless in intermediate strings.
How it fails. Parse "00123" as 123 but reject "0" or mishandle "-0" per spec.
Fix. Strip sign first; handle all-zero -> single "0"; rebuild without leading zeros except zero.
One-way mapping
Why it happens. One dict from s→t feels enough for isomorphism.
How it fails. s="ab", t="cc": map a→c, b→c, t-side conflict not detected.
Fix. Maintain maps in both directions (or check t→s on each assign).
Line rules mixed up
Why it happens. Justify every line the same way.
How it fails. Last line fully justified per middle-line rule, extra spaces where spec says left-align.
Fix. Branch: last line and single-word lines have different spacing rules.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.