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.
Why 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.
The 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 |
A fair caveat
Modern JavaScript engines optimise repeated += with internal rope structures, and the JVM rewrites simple concatenation inside a single expression. Neither rescues a genuine loop over a large collection — and in an interview, naming the O(n2) risk is the point.
Comparing strings correctly
Using == on strings in Java
== compares references, not characters. It appears to work for literals because they are interned, then fails the moment a string arrives from input or is built at runtime. Use .equals(), or .equalsIgnoreCase() when case should not matter.
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
| Problem | Pattern | Level |
|---|---|---|
| Reverse a string in place | Two pointers | Easy |
| Check if two strings are anagrams | Frequency count | Easy |
| Find the first non-repeating character | Frequency count | Easy |
| Compress a string in place (aabcc → a2bc2) | Read/write pointers | Medium |
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 this topic solo, or share a room code and battle friends on it.
⚡ Start the Strings quiz