Lesson 3.2 · Strings

Immutable Strings, StringBuilder and char Arrays

Why string concatenation in loops is slow, and the two efficient tools: StringBuilder for building and char[] for editing in place.

12 min

Think of it like this

A Java String is a printed receipt: to change one character you must print a whole new receipt. A StringBuilder is a notepad you keep writing on, and a char[] is a row of tiles you can rearrange.

1.Why += in a loop is O(n²)

Each s += x creates a new string and copies everything so far. Building a string of n characters this way copies 1 + 2 + ... + n ≈ n²/2 characters. For n = 100,000 that's about 5 billion character copies.

Timing.java

public class Main {
    public static void main(String[] args) {
        int n = 100_000;
        long t0 = System.nanoTime();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append('x');
        long builderMs = (System.nanoTime() - t0) / 1_000_000;

        t0 = System.nanoTime();
        String s = "";
        for (int i = 0; i < n; i++) s += 'x';
        long concatMs = (System.nanoTime() - t0) / 1_000_000;

        System.out.println("same length: " + (sb.length() == s.length()));
        System.out.println("concatenation slower: " + (concatMs > builderMs));
    }
}

Output

same length: true
concatenation slower: true

2.Editing with char[]

When you need to swap, overwrite or sort characters, convert with toCharArray(), work on the array, and convert back with new String(chars) or String.valueOf(chars). All the array techniques (two pointers, read/write pointers) then apply directly.

3.Splitting, trimming and joining

s.trim() removes leading and trailing spaces. s.split("\\s+") splits on runs of whitespace (the argument is a regular expression). String.join(" ", parts) joins with a separator. These are fine to use, but know their cost: each creates new strings, O(n) total.

Split.java

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        String s = "  the sky   is blue ";
        String[] words = s.trim().split("\\s+");
        System.out.println(Arrays.toString(words));
        System.out.println(String.join("-", words));
    }
}

Output

[the, sky, is, blue]
the-sky-is-blue

Remember

Never build strings with += in a loop; use StringBuilder.
Use char[] when you need to modify characters in place.
trim, split and join are O(n) and create new strings.

Common mistakes

Splitting on a single space when input can contain several spaces in a row.
Forgetting that split with a leading space produces an empty first element unless you trim first.

Command Palette

Immutable Strings, StringBuilder and char Arrays

1.Why += in a loop is O(n²)

2.Editing with char[]

3.Splitting, trimming and joining