String Basics

A string from an algorithmic perspective

We are already familiar with basic String operations. For algorithms, three properties matter especially: a string has a length, a position can be accessed by index, and the String object itself is immutable.

String text = "code";

int length = text.length();
char first = text.charAt(0);
char last = text.charAt(length - 1);

Both length() and accessing a character by a known index take O(1). That is why many string algorithms are built around moving indexes rather than constantly creating new strings.

Traversing a string

If every character must be inspected, an ordinary linear pass is enough. For example, this counts the number of digits in text:

int digits = 0;

for (int i = 0; i < text.length(); i++) {
    if (Character.isDigit(text.charAt(i))) {
        digits++;
    }
}

This algorithm makes one pass and runs in O(n), where n is the string length. If character positions matter to the solution, an index-based loop is usually more convenient than an enhanced for loop, because String does not directly support that kind of iteration over char values.

Immutability affects the solution

An individual character inside a String cannot be changed. If an algorithm really needs to rearrange or replace characters, it is convenient to first obtain a mutable representation such as a char[] array.

char[] chars = text.toCharArray();
chars[0] = 'C';

String changed = new String(chars);

And if the result is built gradually, StringBuilder is usually a good fit: it lets us append characters without creating a new string at every step.