Strings Basics

Prev Next

Strings show up in an enormous share of interview problems, and Java's specific behavior — strings are immutable — is a frequent source of accidentally-quadratic code that candidates don't notice until asked to justify their complexity. This lesson covers exactly why that happens and how to avoid it.

Java Strings Are Immutable

Once a String object is created, its character content can never change. Every operation that looks like it "modifies" a string — concatenation, replacement, case conversion — actually allocates a brand-new String object and leaves the original untouched.

String s = "hello";
s = s + " world"; // does NOT mutate "hello" -- allocates a new String "hello world"
// the original "hello" object still exists; s now just points elsewhere

This is why strings are safe to share freely (no one can corrupt a string out from under you) and why they're usable as HashMap keys, but it's also exactly why building a string piece by piece with += is dangerous for performance.

Why s += x in a Loop Is O(n²) — Use StringBuilder

Each += allocates a new string and copies all the characters accumulated so far into it. Doing that n times means the total characters copied is 1 + 2 + 3 + ... + n, which sums to roughly n²/2 — quadratic, even though the loop itself only runs n times.

// O(n^2): every += copies everything accumulated so far into a new String
public String buildBad(int n) {
    String result = "";
    for (int i = 0; i < n; i++) {
        result += i; // allocates a new String each time, copying old content
    }
    return result;
}

// O(n): StringBuilder mutates an internal, resizable char buffer in place
public String buildGood(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
        sb.append(i); // amortized O(1) per append
    }
    return sb.toString();
}

buildBad: Time complexity: O(n²) — the sum of copy costs 1+2+...+n is O(n²). Space complexity: O(n) for the final string (ignoring the discarded intermediate allocations, which is itself extra pressure on the garbage collector).
buildGood: Time complexity: O(n) — each append is amortized O(1) against StringBuilder's internal resizable buffer, same reasoning as ArrayList's growth. Space complexity: O(n) for the internal buffer.

Common String Operations and Their Complexity

Operation	Complexity	Why
charAt(i)	O(1)	Strings are backed by a char array (or byte array, in modern Java's compact strings) — direct indexed access.
length()	O(1)	The length is cached as a field, not recomputed by scanning.
substring(a, b)	O(b − a)	Modern Java (7u6+) copies the relevant characters into a new array, proportional to the substring's length.
indexOf(needle)	O(n · m) worst case	Naive search checks every starting position (n) against the needle (m characters); most JDK implementations don't use a faster string-search algorithm here.
equals(other)	O(min(n, m))	Compares character by character but bails out at the first mismatch (and short-circuits on length difference).

Worked Example: Palindrome Check With Two Pointers

Same two-pointer idea as reversing an array — walk inward from both ends, and if any pair of characters disagrees, it's not a palindrome.

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

Time complexity: O(n) — each character is visited at most once as the two pointers close in from both ends. Space complexity: O(1) — no new string or array is allocated; charAt is a constant-time read against the original string.

String vs StringBuilder vs StringBuffer

Type	Mutable?	Thread-safe?	When to use
String	No	Yes (immutability makes it inherently safe)	Default choice; anywhere you're not building text incrementally in a hot loop.
StringBuilder	Yes	No	Building/mutating text in a loop, single-threaded — the standard choice for interview code.
StringBuffer	Yes	Yes (synchronized methods)	Only when multiple threads mutate the same buffer concurrently; the synchronization overhead is wasted otherwise, so prefer StringBuilder by default.

Next: With arrays and strings covered, we move to a structure that trades array's O(1) indexing for O(1) insertion at the front — Singly Linked List.

Prev Next