Strings
A contiguous array of characters — plus the surprisingly deep question of how you know where it ends.
Prerequisites
- Big-O & Asymptotic Analysis — string work is full of hidden O(n) scans.
- Memory, References & Ownership — a string is a block of bytes; who owns it decides whether it can change.
- Arrays — a string is an array of characters, indexed in O(1).
- Dynamic Arrays & Amortized Growth — builders and growable strings reuse that exact machinery.
The 10-second version
A string is an array of characters — nothing more exotic than that. Reading character i
is O(1), the same address arithmetic as any array. The interesting part is where it ends:
C has no length field at all and marks the end with a sentinel byte (the NUL, \0), so
measuring its length is an O(n) scan. Most modern languages store the length explicitly
and make strings immutable, which turns "append one character" into "allocate a brand-new
string" — O(n) each time. That's why repeated a = a + b in a loop is a hidden O(n²), and why
StringBuilder / join / String::with_capacity exist: they build in one pass.
Why this existed
On early computers, text wasn't one thing. Punch cards and printers had fixed-width fields, so "a string" was just a run of columns — a length you knew from the layout, not something the data carried. Senior languages like FORTRAN kept that flavor; text was handled with explicit counts.
The moment text became a first-class value, everyone had to pick a convention for where does it stop? and the two camps have been arguing ever since:
- 1970 — Niklaus Wirth's Pascal stores each string with a length byte up front
(the famous
string[255]): onestrlen, instant length, but a hard 255-character ceiling. - 1972 — C goes the other way: a string is just a
chararray that happens to end in a NUL byte,'\0'. No length stored, no ceiling, but every length question is a scan. - 1995 — Java makes
Stringimmutable: once created it never changes, which makes sharing and caching safe but makes "modification" mean "allocation." - 2015 — Rust splits the concept cleanly into
&str(a borrowed view: pointer plus length) andString(an owned, growable buffer).
Why it mattered then: the C convention won the systems world and promptly became the source
of the most exploited class of bug in computing history — the buffer overrun. Forget the
terminator, or copy one byte too many, and you're off the end of the array into somebody
else's memory. Heartbleed, dozens of CVEs, entire textbooks — all downstream of one missing
+ 1.
Inside the inventor's head
The design question is tiny and enormous at once: do I store the length, or a sentinel?
Storing the length sounds obviously better, and it mostly is. Pascal's first attempt shows the cost: park the length in one byte and you can never hold more than 255 characters. The C camp looked at that ceiling and said no thanks — trade a fast length for an unbounded one. They got the trade half right: unbounded strings are great, but tying the terminator to ordinary data means a single missing byte silently runs the length off the end.
Then the naive building trick piles on. Watch the trap in code — every one of these is "append a word," and every one of them copies the whole accumulated string:
// Naive: `+` allocates a brand-new string each time — Θ(n²) totalconst buildNaive = (words) => { let out = ""; for (const w of words) out = out + w; // copies `out` every iteration return out;};// Improved: join copies everything exactly once — Θ(total length)const buildFast = (words) => words.join("");The pivot is realizing the work is quadratic for a linear task. Nobody intends to copy the
prefix n times; they intend to append. The fix in every language is the same shape: figure
out how big the result will be, get that memory once, then fill it front to back.
The final approach
The two layouts
Same bytes, different author's contract. C says "read until you hit NUL." Pascal and Rust
say "read exactly len characters."
The invariant
- C strings: the last byte of the contents is
'\0', and everything before it is data.strlen,strcpy, andprintf("%s")all stop at that byte. Break the invariant — forget the terminator — and the string runs into whatever follows it in memory. - Length-prefixed / modern strings: the length field matches the characters. Length is O(1), and indexing anywhere below the length is safe.
A flow: concatenating "cat" and "dog"
A worked trace: strlen("cat") and "cat" + "dog"
| Step | What happens | Cost |
|---|---|---|
strlen("cat") | check c, a, t, then NUL → count 3 | 4 byte reads (O(n)) |
| allocate | 3 + 3 + 1 = 7 bytes | one allocation |
copy a | write c a t | 3 copies |
copy b | write d o g | 3 copies |
| terminate | write '\0' at index 6 | 1 write |
| result | "catdog" of length 6 | Θ(n + m) total |
The + 1 at the end is the whole safety story: one extra byte for the NUL, or a buffer
overrun waiting to happen.
It in code
// JS strings are immutable and carry their length: length is O(1).const myLen = (s) => s.length; // a field, not a scanconst myConcat = (a, b) => a + b; // allocates a NEW string of length |a| + |b|Complexity
| Operation | Best | Average | Worst | Why |
|---|---|---|---|---|
| Length | Θ(1) | Θ(n) | Θ(n) | C scans to the NUL; modern strings cache it |
Index s[i] | Θ(1) | Θ(1) | Θ(1) | contiguous characters |
| Concatenate two strings | Θ(m+n) | Θ(m+n) | Θ(m+n) | both sides must be copied |
Build via repeated + | Θ(n²) | Θ(n²) | Θ(n²) | each + copies everything so far |
Build via builder / join | Θ(n) | Θ(n) | Θ(n) | amortized appends, one allocation |
| Naive substring search | Θ(m) | Θ(n·m) | Θ(n·m) | compare at every starting offset |
The headline contrast the archive keeps coming back to: reading a character is O(1), but changing a string usually isn't. Immutability is a feature — shared, hashable, thread-safe strings — that you pay for in concatenation.
Where you meet it today
- C buffer safety. The
+1for the NUL is whysnprintftakes a size and why "safe" string functions exist at all. Forget it and you write the classic overflow. - Java/JS/Python string building. Because strings are immutable, code that does
result += piecein a loop is a performance bug; the language gives youStringBuilder,join, orStringIOto fix it. - Ropes and gap buffers. Text editors never store a 100 MB file as one flat string; they keep a tree of chunks ("ropes") so an insert in the middle is O(log n), not O(n).
- Rust's
&strvsString. Borrowed views and owned buffers make "who can mutate this text" an explicit, checked decision.
// JS: strings are immutable, so building is producing a new stringconst path = `${dir}/${file}`; // template literalRecap
- A string is an array of characters; indexing is O(1) exactly like an array.
- C marks the end with a NUL byte, so
strlenis O(n); forgetting the terminator causes buffer overruns. Pascal/Rust/Java store the length, so it's O(1). - Immutable strings (Java, JS, Python) make sharing safe but make concatenation O(n) —
repeated
+in a loop is O(n²). - Build with a builder /
join/with_capacityto get O(n) instead of O(n²). - The eternal trade-off: index in O(1), but modifying in the middle or concatenating costs a copy.
Next up: Singly Linked Lists — the structure that gives up O(1) indexing to make inserting and splicing nodes cheap.