Lesson 11new · v2 format
Strings: Build, Count & Match
Strings are arrays of characters with one twist — in Python they can't be changed. Four blocks cover most string problems.
01Why it matters & the intuition
Around a third of interview problems are about strings: anagrams, palindromes, compression, parsing, matching. Most of them reuse array ideas you already have — two pointers, counting, runs — with a few string-specific rules: strings are immutable in Python, characters map to numbers with ord, and building a string one piece at a time must be done carefully.
Think of it like…
A printed page. You can't erase a printed letter — to change a word you type a new page. In Python a string is that printed page: to 'edit' it you gather the new characters in a list (your draft) and print once with join.
02The code blocks
Each block: the template in Python and C++, a line-by-line trace (press play and watch the highlighted line and the variables), the mistakes that cost the most debugging time, and a recall drill. Do the drill without scrolling up— that’s what makes it stick.
Block 1
Build a string with a list + join
Use it for: Any time you create a new string character by character: filtering, transforming, reversing words, encoding.
1 · The template
parts = []
for ch in s:
if ch != " ":
parts.append(ch.upper())
result = "".join(parts)2 · Watch it run, line by line
▶parts = []2for ch in s:3if ch != " ":4parts.append(ch.upper())5result = "".join(parts)
Variables
—
3 · Classic mistakes
result = "" for ch in s: result += chEach += can copy the whole string: O(n²) for long inputs. Collect in a list, join once.s[0] = "X"TypeError: Python strings are immutable. Convert with list(s), edit, then ''.join().
4 · Recall it without looking
parts = []
for ch in s:
parts.(ch)
result = .join(parts)Block 2
Count letters with a 26-slot array
Use it for: Anagrams, 'first unique character', ransom notes, comparing letter frequencies — lowercase a–z input.
1 · The template
count = [0] * 26
for ch in s:
count[ord(ch) - ord("a")] += 12 · Watch it run, line by line
▶count = [0] * 262for ch in s:3count[ord(ch) - ord("a")] += 1
Variables
—
3 · Classic mistakes
count[ord(ch)] += 1ord('a') is 97 — index 97 is out of range. Subtract ord('a') to map a..z to 0..25.Using this on arbitrary Unicode textOnly valid for a known small alphabet. Otherwise use a dict / Counter.
4 · Recall it without looking
count = [0] * 26
for ch in s:
count[ord(ch) - ] += 1Block 3
Group runs of equal characters
Use it for: Run-length encoding, 'longest streak', counting consecutive groups, compressing strings.
1 · The template
i = 0
out = []
while i < len(s):
j = i
while j < len(s) and s[j] == s[i]:
j += 1
out.append(s[i] + str(j - i))
i = j2 · Watch it run, line by line
▶i = 02out = []3while i < len(s):4j = i5while j < len(s) and s[j] == s[i]:6j += 17out.append(s[i] + str(j - i))8i = j
Variables
- i
- 0
3 · Classic mistakes
i += 1 at the end instead of i = jRestarts inside the same run and counts it again ('a3a2a1…').while s[j] == s[i] and j < len(s):Reads s[len(s)] at the end of the string → IndexError. Guard first.
4 · Recall it without looking
while i < len(s):
j = i
while and s[j] == s[i]:
j += 1
out.append(s[i] + str())
i = jBlock 4
Is s a subsequence of t?
Use it for: Matching in order with gaps: subsequence checks, 'can I delete characters to get…', merging two sequences.
1 · The template
i = 0
for ch in t:
if i < len(s) and s[i] == ch:
i += 1
found = i == len(s)2 · Watch it run, line by line
▶i = 02for ch in t:3if i < len(s) and s[i] == ch:4i += 15found = i == len(s)
Variables
- i
- 0
3 · Classic mistakes
if ch in s:Ignores order: 'eca' would pass. You must match s left to right.s[i] == ch without i < len(s)Once all of s is matched, s[i] is out of range on the next character of t.
4 · Recall it without looking
i = 0
for ch in t:
if i < len(s) and s[i] == ch:
found = i == 03Key ideas
Immutable in Python, mutable in C++
s[0] = 'X' fails in Python. Build with a list and ''.join(...). C++ std::string can be edited in place and += a char is cheap.
Characters are numbers
ord('a') = 97, chr(97) = 'a'. ord(ch) - ord('a') maps a–z to 0–25 (C++: ch - 'a'). This is what makes the 26-slot counting array work.
Slicing copies
s[i:j] creates a new string of length j − i. Slicing inside a loop quietly adds an O(n) factor.
Reuse array blocks
Two pointers → palindromes, reverse words. Counting → anagrams. Runs → compression. Sliding window → longest substring without repeats.
04Cheat sheet
Every block from this lesson on one screen. Keep it open while you do the lab — then try the lab again without it.
# build: list + join (never += in a loop)
parts = []
for ch in s:
parts.append(ch)
result = "".join(parts)
# chars <-> numbers
idx = ord(ch) - ord("a") # 'a'..'z' -> 0..25
ch = chr(idx + ord("a"))
# count letters (a-z)
count = [0] * 26
for ch in s:
count[ord(ch) - ord("a")] += 1
# runs of equal characters
i = 0
while i < len(s):
j = i
while j < len(s) and s[j] == s[i]:
j += 1
# run is s[i:j], length j - i
i = j
# subsequence
i = 0
for ch in t:
if i < len(s) and s[i] == ch:
i += 1
is_sub = i == len(s)05Complexity
| Operation | Python | C++ |
|---|---|---|
| s[i], len(s) | O(1) | O(1) |
| s + t, s[i:j], s.replace(…) | O(length) — creates a new string | O(length) |
| result += ch in a loop | O(n²) worst case — use list + join | O(1) amortised |
| ''.join(parts) / building with reserve | O(total length) | O(total length) |
| 26-slot letter count | O(n) time, O(1) space | same |
06Recognise it in a problem
These phrases in a problem statement should make you reach for a specific tool before you write any code.
| If the problem says… | …reach for |
|---|---|
| "anagram", "same letters", "permutation of", lowercase letters only | 26-slot count array (or Counter) |
| "compress", "consecutive repeated characters", "longest streak" | Group runs with i / j |
| "delete some characters to get", "appears in order" | Subsequence two pointers |
| "reads the same backwards", "reverse the words" | Two ends inward (Code Fluency) |
| "longest substring without / with at most k …" | Sliding window + counts |
| Building a long output string piece by piece | List + join (Python) — avoid += in a loop |
07Decode drills
You won’t solve these here. Read each problem the way an experienced engineer would: circle the clues in your head, pick the technique family and the complexity you must hit. Then check the clues you missed.
Scrambled product codes
Two product codes use only lowercase letters. Decide whether one is a rearrangement of the other.
Constraints: length ≤ 5 × 10⁴
08Check your understanding
09Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Run-length encode
Compress a string by replacing each run of equal characters with the character followed by the run length. "aaabcc" → "a3b1c2". Return "" for an empty string. Use the group-runs block and build the result efficiently.