6 of 32 · 5 min

Strings are arrays with sharp edges

A string is an array of characters, and almost everything from the last page applies. The sharp edges are worth knowing before they cut.

Immutability

In Python, Java, JavaScript and C#, a string cannot be changed. Every operation that looks like a change builds a new one.

python

result = ""
for word in words:          # n words
    result += word          # builds a NEW string each time

That loop looks linear and is quadratic. Each += copies everything accumulated so far. For 10,000 words it copies about 50 million characters.

python

result = "".join(words)     # O(n), one allocation

Java has the same trap and the same fix: StringBuilder rather than + in a loop.

Common operations

Operation	Cost
Length	O(1) in most languages
Character at index	O(1)
Concatenate two	O(n + m)
Substring	O(k) for k characters
Find a substring, naive	O(n × m)
Split	O(n)
Reverse	O(n)

Characters are not bytes

len("नमस्ते") does not give you the number of bytes, and in some languages it does not give the number of visible characters either. A UTF-8 character takes one to four bytes; an emoji with a skin tone modifier is several code points that render as one symbol.

For DSA problems this rarely matters. For real input from real people it matters constantly, and assuming one character is one byte is how software breaks on names.