Characters and building strings

Big idea

A string is an array of characters, and each character is really a small number (its code). In Python, Java, and JavaScript strings are also immutable — every "change" builds a new string — so build results in a list or builder and join once.

Characters are numbers

In ASCII and Unicode, 'a' is 97, 'b' is 98, … 'z' is 122; 'A' is 65; '0' is 48. Letters and digits are consecutive, which gives you cheap arithmetic:

c - 'a' is the trick behind 26-slot count arrays (next lesson) and Caesar shifts: shifting by k is (c - 'a' + k) % 26.

Immutability and the += trap

s = "cat"
s[0] = "b"        # TypeError: strings can't be changed in place
s = "b" + s[1:]   # builds a brand-new string "bat"

Because each + makes a new string and copies both sides, this loop is quadratic:

result = ""
for word in words:          # n words
    result += word + " "    # copies everything built so far

The copies are 1 + 2 + 3 + … + n characters' worth — O(n²) for n characters of output. Collect pieces and join once instead:

parts = []
for word in words:
    parts.append(word)      # O(1) amortized
result = " ".join(parts)    # one O(n) copy

C++ std::string is mutable, and s += x appends in amortized O(1) — but s = s + x still builds a copy.

Watch it

Compare repeated += with collecting pieces and joining once.

Turning a string into an array

When you need to swap or overwrite characters, convert first:

chars = list(s)           # mutable copy, O(n)
chars[0], chars[-1] = chars[-1], chars[0]
s = "".join(chars)

In Java use s.toCharArray() and new String(arr).

Comparing strings

• a == b compares content in Python and C++. In Java, == compares references — use a.equals(b).
• Comparing two strings costs O(length), not O(1). Sorting n strings of length k is O(n log n × k).
• Slicing s[i:j] copies j − i characters. A loop that slices every time is hiding an O(n) inside.

Practice

• Length of Last Word — scan from the end, no splitting needed.
• Reverse Words in a String — split, reverse the list, join.
• Add Strings — digit arithmetic with c - '0' and a carry.

Quick check