Strings and character encoding

A string is a sequence of characters — the text your program works with. Every time you write "hello", store a user’s name, or read a line from a file, you’re working with a string. In most languages, you create strings by wrapping text in quotes:

greeting = "hello"     # a string with 5 characters
name = "Pratik"        # another string
empty = ""             # a string with 0 characters (still a valid string!)

That’s the surface level — and it’s all most tutorials cover. But as a programmer, you need to understand what happens under the hood: how those characters are stored in memory, why some operations are fast and others secretly slow, and why an emoji can break code that works perfectly on English text. This post connects strings to what you already know from the arrays and memory posts, and reveals the traps waiting in innocent-looking string code.

Strings are array-like, but with important extra rules

The easiest mental model is: a string is an array of character data. That connects directly to the arrays post: elements sit in memory, indexing means “jump to the right place,” and contiguous storage is fast because of cache locality.

Just like iterating through a number array, you can loop through a string character by character:

The catch is that “character” is trickier than “integer.” With an integer array, every element is the same size. With text, the bytes in memory depend on the character encoding. If the encoding is fixed-width, indexing is simple. If the encoding is variable-width, “give me the 10th character” may require walking through earlier bytes first.

So strings are array-like, but they also carry an interpretation layer:

1. Raw bytes in memory
2. An encoding rule telling us what those bytes mean
3. Often a stored length so the runtime knows where the string ends

That extra layer is why strings deserve their own post instead of being treated as “just arrays.”

Character encoding: turning symbols into bytes

Computers store bytes, not letters. An encoding is the mapping from human-readable symbols to numeric byte patterns.

ASCII: the original common baseline

ASCII uses 7 bits, so it can represent 128 characters: English letters, digits, punctuation, and control characters like newline.

For plain English text, ASCII is beautifully simple: one character fits in one byte, and the top bit stays 0.

Extended ASCII vs Unicode

Once software needed accented letters, non-Latin scripts, and symbols, ASCII stopped being enough. “Extended ASCII” tried to use 8 bits for 256 values, but different systems assigned those extra values differently. The same byte could mean one symbol on one machine and something else on another.

Unicode solved the meaning problem by defining a giant universal character set: A, é, न, 中, and 😀 each get their own code point. But Unicode does not say how those code points must be stored as bytes. That is the job of encodings like UTF-8 and UTF-16.

UTF-8: variable-width, backward-compatible, everywhere

UTF-8 is the dominant encoding on the web because it keeps ASCII unchanged while supporting the entire Unicode range. It uses 1 to 4 bytes per code point.

That pattern matters. A leading byte tells you how many bytes belong to the current code point, and continuation bytes always start with 10.

So the string "A😀" is 5 bytes in UTF-8, not 2. That single fact explains a lot of “why is string indexing weird?” questions.

Step through this visualization to see exactly how many bytes each character takes:

flowchart LR
T["Text: A😀"] --> CP["Code points<br/>U+0041, U+1F600"]
CP --> B["UTF-8 bytes<br/>41 F0 9F 98 80"]
B --> M["Memory layout<br/>[41][F0][9F][98][80]"]

Why indexing is not as simple as it looked in arrays

In the arrays post, index i meant: base + i × element_size. That works because every element has equal width.

With strings, the real question is: what exactly are you indexing?

• If you index raw bytes, UTF-8 gives O(1) access to byte i.
• If you index characters/code points in a variable-width encoding, the runtime may need to scan from the start to find where the ith character begins.
• If you index grapheme clusters (what humans think of as one visible character), things get even harder: some “characters” are actually multiple code points combined.

This is why the “true” complexity story is more subtle than most interview prep summaries suggest. For a fixed-width character array such as ASCII bytes, access by character index is O(1). For a variable-width byte encoding like UTF-8, access by character position is often O(n).

That is not just theory. If you repeatedly ask for the 50,000th code point in a long UTF-8 buffer, the program may have to walk many earlier bytes every time.

String immutability: why most languages make new strings instead of changing old ones

In Python, Java, and Go, strings are effectively immutable: once created, their contents do not change.

That sounds annoying until you see the benefits:

• Safety: two variables can share the same string without worrying that one changes it behind the other’s back.
• Hashing: immutable strings can be safely used as dictionary/map keys because their value won’t mutate after hashing.
• Optimization: runtimes can share storage, cache hash values, and intern common strings.

s = "cat"
t = s
s += "s"

print(s)  # "cats"
print(t)  # "cat"

"cat" was not modified in place. A new string "cats" was created, and s now points to it.

The O(n²) trap: s += "x" inside a loop

Because strings are immutable, concatenation usually means allocating a new buffer and copying old data plus new data into it.

If you do this once, it is fine. If you do it in a loop, the costs pile up:

• after 1 append, copy 1 character
• after 2 appends, copy 2 characters
• after 3 appends, copy 3 characters
• …
• after n appends, total work is 1 + 2 + 3 + ... + n = O(n²)

Watch the copies pile up in this step-through — notice how the total work grows quadratically:

This is one of the most common performance mistakes beginners make with strings.

String interning and pools

Because immutable strings are safe to share, runtimes often reuse identical ones.

• Java keeps string literals in a string pool.
• Python interns some strings, especially identifier-like or small frequently used ones, though the exact behavior is implementation-dependent.

String a = "hello";
String b = "hello";
System.out.println(a == b); // often true for pooled literals

This reuse saves memory, but it does not change the complexity of building new strings repeatedly.

Common string operations and their true complexity

String operations are often taught too casually. The right answer depends on encoding and representation, but this table is the most useful general mental model.

A few caveats matter:

• Some languages return slices as views in special cases, but many modern runtimes copy to avoid accidental memory retention bugs.
• In Java, indexing is O(1) by UTF-16 code unit, not necessarily by full Unicode character or grapheme cluster.
• In Python, strings behave like sequences of Unicode code points, but the internal representation is optimized and implementation-specific.

The key lesson is: never assume “string = free random access array of visible characters.” That assumption quietly breaks for real-world Unicode text.

StringBuilder and StringBuffer: the escape hatch from quadratic concatenation

If repeated concatenation is expensive, the natural fix is: don’t rebuild the whole string every time.

That is exactly what StringBuilder in Java and “build a list, then join” in Python do. Underneath, the idea is basically a dynamic array of characters or chunks. You append pieces into a resizable buffer, and only at the end do you produce one final string.

So this section secretly loops back to the dynamic arrays post: the performance win comes from amortized-efficient appends into a growable buffer.

# Wrong: repeated string concatenation
s = ""
for ch in ["a", "b", "c", "d"]:
    s += ch

# Right: collect pieces, join once
parts = []
for ch in ["a", "b", "c", "d"]:
    parts.append(ch)
s = "".join(parts)

// Wrong: creates many temporary strings
String s = "";
for (String ch : new String[]{"a", "b", "c", "d"}) {
    s += ch;
}

// Right: append into a mutable buffer
StringBuilder sb = new StringBuilder();
for (String ch : new String[]{"a", "b", "c", "d"}) {
    sb.append(ch);
}
String s = sb.toString();

StringBuffer is similar to StringBuilder but synchronized for thread safety, so it usually has a bit more overhead. In single-threaded code, StringBuilder is the common choice.

The big idea is not the class name. The big idea is: use a mutable staging buffer when constructing text incrementally.

Null-terminated strings vs length-prefixed strings

Different languages store string boundaries differently.

In C, a string is usually a sequence of bytes ending with a special '\0' null byte.

char name[] = {'c', 'a', 't', '\0'};

To find the length, functions like strlen scan until they hit that terminator. That makes length computation O(n) unless you already stored it somewhere else.

Modern languages usually use length-prefixed strings: the runtime stores the length separately along with the bytes. That makes getting len(s) or s.length() typically O(1).

flowchart TD
A["C-style null-terminated<br/>['c']['a']['t']['\0']"] --> A1["Length? scan until \0"]
B["Length-prefixed<br/>len = 3, bytes = ['c']['a']['t']"] --> B1["Length? read stored metadata"]

Null-terminated strings are compact and simple at the systems level, but they come with classic pitfalls:

• forgetting the terminator
• buffer overflows
• accidental truncation when binary data contains '\0'

Length-prefixed strings avoid many of those problems and fit modern language runtime needs much better.

Putting it all together

A string is not just “text.” It is a data structure with:

• a memory layout
• an encoding
• mutability rules
• operation costs that depend on representation

That is why strings show up everywhere in interviews and performance bugs alike. If you understand arrays, dynamic arrays, and memory, strings stop feeling magical.

Key takeaways

1. Strings are array-like, but characters are encoded bytes, not fixed-size integers.
2. ASCII is 7-bit and tiny; Unicode defines characters broadly; UTF-8 is the common variable-width encoding that uses 1 to 4 bytes.
3. In UTF-8, 'A' is 1 byte but 😀 is 4 bytes, so “number of bytes” and “number of characters” are not the same thing.
4. Immutable strings are safer and easier for runtimes to optimize, but repeated concatenation can create the classic O(n²) trap.
5. StringBuilder, StringBuffer, and Python’s "".join(...) pattern work because they use a mutable growable buffer underneath.
6. Null-terminated strings and length-prefixed strings lead to different complexity tradeoffs, especially for length calculation.

Practice problems

• Valid Anagram (Easy) — frequency counting and equality of character multiset
• Reverse String (Easy) — in-place character swapping
• Longest Substring Without Repeating Characters (Medium) — sliding window over string data
• Implement strStr() (Easy) — a good warm-up before learning KMP

What’s next

Next up: string manipulation patterns — the recurring techniques behind substring search, sliding windows, two pointers, frequency maps, and palindrome-style questions. Once you understand how strings are stored, the next step is learning how to work with them efficiently.