Course contents
String Immutability and Why Concatenation Is Slow
In Java, Python, C# and JavaScript, a string cannot be modified after it is created. Every operation that looks like a change actually builds a new string. Understanding that turns a mysterious performance problem into an obvious one.
01Why immutability exists
- Safe sharing. Many references can point at one string with no risk of one holder changing it under another.
- Cacheable hash codes. The hash can be computed once and reused, which is what makes strings good hash-map keys.
- Interning. Identical literals can share one object in memory.
- Thread safety for free. Nothing can mutate, so nothing needs locking.
02The concatenation trap
// O(n^2): every += allocates a new string and copies everything so far
String slow = "";
for (String part : parts) {
slow += part;
}
// O(n): one growable buffer, one final copy
StringBuilder sb = new StringBuilder();
for (String part : parts) {
sb.append(part);
}
String fast = sb.toString();On iteration i the naive loop copies i characters. Summed over n iterations that is n(n+1)/2 copies — O(n2). With 100,000 parts, the difference is the gap between milliseconds and minutes.
| Language | Use | Avoid in a loop |
|---|---|---|
| Java | StringBuilder.append() | s += part |
| Python | "".join(parts) | s += part |
| C++ | s.append() with reserve() | s = s + part |
| JavaScript | parts.join('') | s += part over very large inputs |
03Comparing strings correctly
Python's == compares by value and is correct; is compares identity and is the equivalent trap. C++ std::string overloads == to compare contents, but comparing two char* pointers compares addresses.
Key takeaways
- Immutability buys safe sharing, cached hashes and thread safety.
- Concatenating in a loop is O(n squared); a builder or join makes it O(n).
- In Java, compare with .equals() — == compares references.
- Most string algorithms are array algorithms once you convert to a character array.
Practice problems
Tagged by pattern, so you can tell whether you learned the idea or just the example.
- Reverse a string in placeTwo pointersEasy
- Check if two strings are anagramsFrequency countEasy
- Find the first non-repeating characterFrequency countEasy
- Compress a string in place (aabcc → a2bc2)Read/write pointersMedium
Frequently asked questions
Why are strings immutable in Java and Python?
Immutability lets strings be shared freely between references and threads without defensive copying, allows the hash code to be cached so strings work well as map keys, and enables interning of identical literals.
Why is string concatenation in a loop O(n squared)?
Each concatenation allocates a new string and copies everything accumulated so far. Copy lengths 1, 2, 3 ... n sum to n(n+1)/2, which is quadratic.
What is the difference between String, StringBuilder and StringBuffer?
String is immutable. StringBuilder is a mutable buffer designed for building strings efficiently in a single thread. StringBuffer is the same idea with synchronised methods, which makes it thread-safe but slower.
Test yourself on Strings
Reading is not recall. Take a timed quiz on Strings solo, or share a room code and battle friends on it.