Everyday string operations and what they cost

Every language gives strings a large toolbox. The tools are easy to use and easy to misuse: a single call can hide a full pass over the string, and inside a loop that turns O(n) into O(n²). Here is what each everyday operation is called in the four languages, and what it costs. n is the length of the string.

Reading

Length — s.length · len(s) · s.length() · s.size() — O(1): stored with the string.
Character at i — s[i] · s[i] · s.charAt(i) · s[i] — O(1).
Loop over characters — for (const ch of s) · for ch in s · for (char ch : s.toCharArray()) · for (char ch : s) — O(n). (Java's toCharArray() makes a copy; a plain index loop with charAt doesn't.)

Making new strings

All of these return a new string (except in C++ where noted), so each one costs at least the length of what it produces.

Substring — s.slice(a, b) · s[a:b] · s.substring(a, b) · s.substr(a, len) — O(b - a): it copies those characters.
Concatenate — s + t in all four — O(n + m).
Upper / lower case — toUpperCase() · upper() · toUpperCase() · toupper(c) per character — O(n).
Trim spaces at the ends — trim() · strip() · trim() · (no built-in in C++) — O(n).
Replace — replaceAll(a, b) · replace(a, b) · replace(a, b) · loop with — for simple text.

The string string with indexes 0 to 5. The substring from index 1 up to but not including 4 is t, r, i, highlighted. JavaScript slice(1, 4), Python [1:4] and Java substring(1, 4) all give tri. C++ substr(1, 3) also gives tri because its second argument is a length, not an end index.

Searching

Find a substring — s.indexOf(t) · s.find(t) · s.indexOf(t) · s.find(t) — returns the first index or -1 (std::string::npos in C++). O(n · m) in the worst case for a pattern of length m; Pattern 8 shows how to do it in O(n + m).
Contains — s.includes(t) · t in s · s.contains(t) · s.find(t) != npos — same cost as find.
Starts / ends with — startsWith(t) · startswith(t) · startsWith(t) · s.rfind(t, 0) == 0 — O(m).

Splitting and joining

Split into words — s.split(" ") · s.split() · s.split(" ") · read with a stringstream — O(n), and it builds a list of new strings.
Join a list — parts.join(" ") · " ".join(parts) · String.join(" ", parts) · append in a loop — O(total length).

Comparing

Equal? — s === t · s == t · s.equals(t) · s == t — O(n): characters are compared until one differs. In Java, == only checks whether two variables point at the same object — always use equals.
Which comes first? — s < t · s < t · s.compareTo(t) < 0 · s < t — lexicographic order, like a dictionary: compare character by character, and a prefix comes before the longer word ("app" < "apple"). Uppercase letters come before lowercase, because their codes are smaller.
Sort the characters — [...s].sort().join("") · "".join(sorted(s)) · Arrays.sort(chars) · sort(s.begin(), s.end()) — O(n log n).

Checking characters

Letter or digit? — /[a-z0-9]/i.test(ch) · ch.isalnum() · Character.isLetterOrDigit(ch) · isalnum(ch).
Digit value — ch - '0' in Java and C++, Number(ch) in JavaScript, int(ch) in Python.
Change case of one character — ch.toLowerCase() · ch.lower() · Character.toLowerCase(ch) · tolower(ch).

Putting it together

A typical small task uses several tools at once. This one tidies a sentence: split it into words on any run of spaces, make each word start with a capital and continue in lower case, and join them with single spaces.

1function titleCase(s) {2  const words = s.trim().split(/\s+/);          // split on runs of whitespace: O(n)3  const out = [];4  for (const w of words) {5    if (w === "") continue;                     // an all-space input gives one empty word6    out.push(w[0].toUpperCase() + w.slice(1).toLowerCase());7  }8  return out.join(" ");                         // one O(n) join at the end9}

JavaScript9 lines

Time O(n), space O(n). Every character is read a constant number of times: once by the split, once by the case changes, once by the join. Notice that none of these tools was called inside a loop over the whole string — that's the habit that keeps string code linear.

Prev Next

Was this helpful?