Algorithm

String Mutability & String Builder

Language Basics & Mechanics Pattern

String Mutability & String Builder

Learn how strings are stored in memory, why string concatenation inside loops leads to O(N^2) time complexity in immutable languages, and how to optimize with String Builders.

CONSTRAINTS
  • Immutable Strings: Java, Python, JavaScript, Go (creates a new string object on every modification)
  • Mutable Strings: C++ (std::string supports in-place modifications)
EXAMPLE 1
Input: Build string of length 100,000 using 'a'
Output: O(N) with StringBuilder vs O(N^2) with s += 'a'
StringBuilder resizes dynamic memory capacity exponentially to achieve O(1) amortized appends.
Is C++ std::string immutable?
No! C++ std::string is mutable and behaves like a vector<char>, allowing in-place mutations like str[0] = 'x'.

A classic performance bug in coding interviews is repeatedly concatenating characters onto a string inside a loop.

The O(N^2) Concatenation Trap

In Java, Python, and JavaScript, strings are immutable.
Doing s += char inside an N-iteration loop allocates a new string of length i and copies all previous characters.
Total work = 1 + 2 + 3 + ... + N = O(N^2) time complexity!

The O(N) Fix

- Java: Use StringBuilder and call .append().
- Python: Append characters to a list and join with "".join(list).
- JavaScript: Push to an array and call array.join("").
- C++: std::string is mutable, so s += c operates in $O(1)$ amortized time.

Interactive Strategy Visualization
🚧

Simulation Under Construction

This algorithm visualization is currently being built by our engineering team. We are ensuring it meets our high-fidelity standards for multi-language parity.

High FidelityMulti-LanguageInteractive
String immutability & StringBuilder optimizations.