Strings and encodings

A string is an array plus an agreement

To a computer, text is a sequence of numbers. A string is an array of those numbers, stored contiguously like any other array, together with an agreement about which number means which character. That agreement is the encoding, and getting it wrong is how text turns into é and �.

The first widely used agreement was ASCII (1963): 128 characters, enough for English letters, digits, punctuation and control codes, each stored in one byte. With one byte per character, a string really is a simple array: character i is byte i, and the length in characters equals the length in bytes. Nearly every other language's text needs more than 128 characters, though.

Unicode: one number per character

Unicode assigns a number, called a code point, to every character in every writing system, plus symbols and emoji. Code points are written as U+ followed by hexadecimal: h is U+0068, é is U+00E9, 😀 is U+1F600. There is room for 1,114,112 code points, and about 150,000 are assigned.

Unicode says which number each character gets. It doesn't say how to store those numbers as bytes. Three encodings do that.

UTF-8

UTF-8 stores each code point in 1 to 4 bytes:

The trace above encodes "hé😀" this way: one byte for h, two for é, four for the emoji, seven in all. The design has three properties that made UTF-8 the encoding of the web, used by about 98% of web pages:

• ASCII is unchanged. Any ASCII file is already valid UTF-8, and English text takes no more space than before.
• It resynchronizes. The first byte of a character never starts with the bits 10, and every continuation byte does. From any position, a program can skip continuation bytes to find the next character boundary.
• Byte order doesn't matter. It is a sequence of single bytes, so there is no little-endian or big-endian version.

The price is that characters have different widths. Character number 1,000 is not at byte 1,000, and the only way to find it is to walk from the start, as the trace's last step shows. Indexing by character is O(n) in UTF-8.

UTF-16 and UTF-32

UTF-16 uses 16-bit units: one unit for code points up to 65,535 and two units, called a surrogate pair, for the rest, including most emoji. Java, JavaScript, C# and Windows store strings this way, because they were designed when Unicode was expected to fit in 16 bits. UTF-32 uses 4 bytes for every code point, so indexing is O(1), at the cost of four times the memory for English text. It is rarely used for storage.

What "length" means in your language

Because each language picked a different representation, the same string has different lengths:

Python achieves O(1) indexing by code point with a trick: each string is stored with 1, 2 or 4 bytes per character, chosen from the widest character it contains, so an ASCII string still costs one byte per character. Go and Rust keep UTF-8 internally and make you choose explicitly between bytes and characters: indexing a Go string gives a byte, and ranging over it gives code points.

Even code points are not always what a reader calls a character. é can also be written as e followed by a combining accent, two code points that display as one. A family emoji such as 👨‍👩‍👧 is five code points: three people joined by two invisible joiners. What users see as one character is a grapheme cluster, and counting those needs a Unicode library. When you truncate text for display, truncate by grapheme cluster; when you store or transmit it, count bytes.

Immutability and building strings

In Java, Python, JavaScript, C# and Go, strings are immutable: once created, they never change. That makes them safe to share and to use as hash keys, but it means every modification creates a new string. Concatenating inside a loop, s = s + c, copies everything built so far on every pass: O(n²) for n characters.

The fix is a dynamic array of characters: StringBuilder in Java and C#, strings.Builder in Go, a list of pieces joined once with "".join(parts) in Python, or an array joined with parts.join("") in JavaScript. Each append is amortized O(1), exactly like the previous lessons' dynamic arrays, and the final string is built once.

Two more costs follow from strings being arrays. Comparing two strings, or hashing one, reads characters one by one, so it is O(length), not O(1). And a substring in most modern languages is a copy, so slicing inside a loop is a hidden O(n). Go is an exception: its substrings share the original string's bytes, which is cheap but keeps the whole original alive in memory.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Strings and encodings from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

s = "hé😀"
data = s.encode("utf-8")
len(s)       # 3 code points
len(data)    # 7 bytes

#include <vector>
#include <algorithm>
 
long long processArrayInvariants(std::vector<int>& nums) {
    long long acc = 0;
    int lo = 0, hi = static_cast<int>(nums.size()) - 1;
    while (lo <= hi) {
        acc += nums[lo];
        if (lo < hi) acc += nums[hi];
        ++lo; --hi;
    }
    return acc;
}

public class ArrayInvariantSolver {
    public static long processArrayInvariants(int[] nums) {
        long acc = 0;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            acc += nums[lo];
            if (lo < hi) acc += nums[hi];
            lo++; hi--;
        }
        return acc;
    }
}

def process_array_invariants(nums: list[int]) -> int:
    acc = 0
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        acc += nums[lo]
        if lo < hi:
            acc += nums[hi]
        lo += 1
        hi -= 1
    return acc

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.