9.02Beginner / Intermediate11 topics20 min9 interactive animations

Core operations

The String methods every algorithm uses: length, charAt, substring, indexOf, contains, startsWith, endsWith, split, join, comparison and trimming, with their costs and edge cases.

Learning goals

Use the core String methods with correct indexes
Know the cost of each operation
Handle split's edge cases
Compare strings correctly

Prerequisites

String fundamentals

9.02.1

Length

s.length() returns the number of UTF-16 code units, in O(1) because the length is stored. For text outside the BMP (emoji) this is not the number of characters. The last valid index is length() - 1, and an empty string has length 0.

Compare with arrays, where length is a field, not a method.

Java

1String s = "algorithm";
2int n = s.length();         // 9
3boolean empty = s.isEmpty();   // false: same as length() == 0
4boolean blank = "  ".isBlank();  // true (Java 11): only whitespace

substring(begin, end): inclusive start, exclusive end

Interactive · edit the input

char[] s · length 9

012345678

In the substringUntouched

Setup

s.length() is 9. Valid indexes are 0 to 8, and end may equal 9 because it is exclusive.

Step 1 / 4

Java

1String sub = s.substring(begin, end);      // begin inclusive, end exclusive
2int length = end - begin;                    // length of the result
3char first = s.charAt(begin);                // StringIndexOutOfBoundsException when begin >= s.length()

Live state

s.length()

begin

end

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L1	s.length()=9 begin=2 end=6	s.length() is 9. Valid indexes are 0 to 8, and end may equal 9 because it is exclusive.
2	L1	begin=2 end=6	Characters 2 to 5 are copied into a new string "gori".
3	L2	length=4	Length = end - begin = 6 - 2 = 4.
4	L3	return="gori"	Result "gori". substring creates a new String (copying 4 chars), O(length).

9.02.2

charAt

s.charAt(i) returns the char at index i in O(1) and throws StringIndexOutOfBoundsException when i < 0 or i >= length(). It returns a UTF-16 code unit, so half of a surrogate pair can come back for emoji.

Loop with charAt or toCharArray(); calling charAt in a loop is as fast as array access.

Java

1String s = "hello";
2char first = s.charAt(0);                // 'h'
3char last = s.charAt(s.length() - 1);    // 'o'
4int vowels = 0;
5for (int i = 0; i < s.length(); i++) if ("aeiou".indexOf(s.charAt(i)) >= 0) vowels++;   // 2

substring(begin, end): inclusive start, exclusive end

Interactive · edit the input

char[] s · length 9

012345678

In the substringUntouched

Setup

s.length() is 9. Valid indexes are 0 to 8, and end may equal 9 because it is exclusive.

Step 1 / 4

Java

1String sub = s.substring(begin, end);      // begin inclusive, end exclusive
2int length = end - begin;                    // length of the result
3char first = s.charAt(begin);                // StringIndexOutOfBoundsException when begin >= s.length()

Live state

s.length()

begin

end

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L1	s.length()=9 begin=2 end=6	s.length() is 9. Valid indexes are 0 to 8, and end may equal 9 because it is exclusive.
2	L1	begin=2 end=6	Characters 2 to 5 are copied into a new string "gori".
3	L2	length=4	Length = end - begin = 6 - 2 = 4.
4	L3	return="gori"	Result "gori". substring creates a new String (copying 4 chars), O(length).

9.02.3

substring

s.substring(begin, end) returns the characters from begin (inclusive) to end (exclusive); s.substring(begin) runs to the end. The result length is end - begin. Since Java 7 substring copies the characters, so it costs O(length of the result) and does not keep the original alive.

Slice with different begin and end values and notice the empty result when begin equals end.

Java

1String s = "algorithm";
2String a = s.substring(2, 6);   // "gori"
3String b = s.substring(4);      // "rithm"
4String c = s.substring(3, 3);   // "" (empty, allowed)
5// s.substring(5, 2) throws StringIndexOutOfBoundsException

substring(begin, end): inclusive start, exclusive end

Interactive · edit the input

char[] s · length 9

012345678

In the substringUntouched

Setup

s.length() is 9. Valid indexes are 0 to 8, and end may equal 9 because it is exclusive.

Step 1 / 4

Java

1String sub = s.substring(begin, end);      // begin inclusive, end exclusive
2int length = end - begin;                    // length of the result
3char first = s.charAt(begin);                // StringIndexOutOfBoundsException when begin >= s.length()

Live state

s.length()

begin

end

No condition evaluated on this step

Execution trace (dry run table)Show 4 steps

Step	Line	State	What happens
1	L1	s.length()=9 begin=2 end=6	s.length() is 9. Valid indexes are 0 to 8, and end may equal 9 because it is exclusive.
2	L1	begin=2 end=6	Characters 2 to 5 are copied into a new string "gori".
3	L2	length=4	Length = end - begin = 6 - 2 = 4.
4	L3	return="gori"	Result "gori". substring creates a new String (copying 4 chars), O(length).

9.02.4

indexOf

indexOf(String or char) returns the index of the first occurrence, or -1. indexOf(x, from) starts searching at from, and lastIndexOf searches from the end. The simple search tries every alignment, O(n·m) worst case.

Watch the pattern slide along the text and stop at the first full match.

Java

1String s = "abcabcabd";
2int i = s.indexOf("abd");        // 6
3int j = s.indexOf('c', 3);       // 5: search from index 3
4int k = s.lastIndexOf("abc");   // 3
5int none = s.indexOf("zzz");    // -1

indexOf, startsWith and endsWith by sliding the pattern

Interactive · edit the input

char[] s · length 9

012345678

ComparingMatchedMismatch

p = "abd"

Setup

Try 7 alignments of p inside s. The first full match wins.

Step 1 / 15

Java

1static int indexOf(String s, String p) {
2    for (int i = 0; i + p.length() <= s.length(); i++) {      // every alignment of p inside s
3        int j = 0;
4        while (j < p.length() && s.charAt(i + j) == p.charAt(j)) j++;
5        if (j == p.length()) return i;                         // all characters matched
6    }
7    return -1;                                                  // contains(p) is indexOf(p) >= 0
8}
9// startsWith checks only i = 0; endsWith checks only i = s.length() - p.length()

Live state

s.length()

p.length()

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L2	s.length()=9 p.length()=3	Try 7 alignments of p inside s. The first full match wins.
2	L4	i=0 j=0	'a' matches p[0].
3	L4	i=0 j=1	'b' matches p[1].
4	L4	i=0 j=2	'c' != 'd': this alignment fails.
5	L4	i=1 j=0	'b' != 'a': this alignment fails.
6	L4	i=2 j=0	'c' != 'a': this alignment fails.
7	L4	i=3 j=0	'a' matches p[0].
8	L4	i=3 j=1	'b' matches p[1].
9	L4	i=3 j=2	'c' != 'd': this alignment fails.
10	L4	i=4 j=0	'b' != 'a': this alignment fails.
11	L4	i=5 j=0	'c' != 'a': this alignment fails.
12	L4	i=6 j=0	'a' matches p[0].
13	L4	i=6 j=1	'b' matches p[1].
14	L4	i=6 j=2	'd' matches p[2].
15	L5	return=6	All 3 characters matched at i = 6: return 6.

9.02.5

contains

s.contains(sub) returns true when sub occurs anywhere in s; it is indexOf(sub) >= 0. It takes a CharSequence, so it also accepts a StringBuilder. For case-insensitive tests lower-case both sides first.

Use the not-found preset: every alignment fails.

Java

1boolean has = "interview".contains("view");          // true
2boolean ci = "Hello".toLowerCase().contains("ell");     // true
3boolean missing = "abc".contains("d");                  // false

indexOf, startsWith and endsWith by sliding the pattern

Interactive · edit the input

char[] s · length 9

012345678

ComparingMatchedMismatch

p = "abd"

Setup

Try 7 alignments of p inside s. The first full match wins.

Step 1 / 15

Java

1static int indexOf(String s, String p) {
2    for (int i = 0; i + p.length() <= s.length(); i++) {      // every alignment of p inside s
3        int j = 0;
4        while (j < p.length() && s.charAt(i + j) == p.charAt(j)) j++;
5        if (j == p.length()) return i;                         // all characters matched
6    }
7    return -1;                                                  // contains(p) is indexOf(p) >= 0
8}
9// startsWith checks only i = 0; endsWith checks only i = s.length() - p.length()

Live state

s.length()

p.length()

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L2	s.length()=9 p.length()=3	Try 7 alignments of p inside s. The first full match wins.
2	L4	i=0 j=0	'a' matches p[0].
3	L4	i=0 j=1	'b' matches p[1].
4	L4	i=0 j=2	'c' != 'd': this alignment fails.
5	L4	i=1 j=0	'b' != 'a': this alignment fails.
6	L4	i=2 j=0	'c' != 'a': this alignment fails.
7	L4	i=3 j=0	'a' matches p[0].
8	L4	i=3 j=1	'b' matches p[1].
9	L4	i=3 j=2	'c' != 'd': this alignment fails.
10	L4	i=4 j=0	'b' != 'a': this alignment fails.
11	L4	i=5 j=0	'c' != 'a': this alignment fails.
12	L4	i=6 j=0	'a' matches p[0].
13	L4	i=6 j=1	'b' matches p[1].
14	L4	i=6 j=2	'd' matches p[2].
15	L5	return=6	All 3 characters matched at i = 6: return 6.

9.02.6

startsWith

s.startsWith(prefix) is true when s begins with prefix; startsWith(prefix, offset) checks at an offset. It needs only one alignment, so it costs O(prefix length). Every string starts with the empty string.

Choose startsWith in the animation: only alignment 0 is tried.

Java

1boolean a = "interview".startsWith("inter");     // true
2boolean b = "interview".startsWith("view", 5);   // true: checked at offset 5
3boolean c = "abc".startsWith("");                  // true

indexOf, startsWith and endsWith by sliding the pattern

Interactive · edit the input

char[] s · length 9

012345678

ComparingMatchedMismatch

p = "abd"

Setup

Try 7 alignments of p inside s. The first full match wins.

Step 1 / 15

Java

1static int indexOf(String s, String p) {
2    for (int i = 0; i + p.length() <= s.length(); i++) {      // every alignment of p inside s
3        int j = 0;
4        while (j < p.length() && s.charAt(i + j) == p.charAt(j)) j++;
5        if (j == p.length()) return i;                         // all characters matched
6    }
7    return -1;                                                  // contains(p) is indexOf(p) >= 0
8}
9// startsWith checks only i = 0; endsWith checks only i = s.length() - p.length()

Live state

s.length()

p.length()

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L2	s.length()=9 p.length()=3	Try 7 alignments of p inside s. The first full match wins.
2	L4	i=0 j=0	'a' matches p[0].
3	L4	i=0 j=1	'b' matches p[1].
4	L4	i=0 j=2	'c' != 'd': this alignment fails.
5	L4	i=1 j=0	'b' != 'a': this alignment fails.
6	L4	i=2 j=0	'c' != 'a': this alignment fails.
7	L4	i=3 j=0	'a' matches p[0].
8	L4	i=3 j=1	'b' matches p[1].
9	L4	i=3 j=2	'c' != 'd': this alignment fails.
10	L4	i=4 j=0	'b' != 'a': this alignment fails.
11	L4	i=5 j=0	'c' != 'a': this alignment fails.
12	L4	i=6 j=0	'a' matches p[0].
13	L4	i=6 j=1	'b' matches p[1].
14	L4	i=6 j=2	'd' matches p[2].
15	L5	return=6	All 3 characters matched at i = 6: return 6.

9.02.7

endsWith

s.endsWith(suffix) is true when s ends with suffix: the only alignment tried is length - suffix.length(). It is handy for file extensions. A suffix longer than the string is never a match.

Choose endsWith in the animation and see the single alignment at the end.

Java

1boolean txt = "report.txt".endsWith(".txt");   // true
2boolean longer = "ab".endsWith("xab");        // false: suffix is longer than the string
3String ext = name.substring(name.lastIndexOf('.') + 1);   // extension, assuming a dot exists

indexOf, startsWith and endsWith by sliding the pattern

Interactive · edit the input

char[] s · length 9

012345678

ComparingMatchedMismatch

p = "abd"

Setup

Try 7 alignments of p inside s. The first full match wins.

Step 1 / 15

Java

1static int indexOf(String s, String p) {
2    for (int i = 0; i + p.length() <= s.length(); i++) {      // every alignment of p inside s
3        int j = 0;
4        while (j < p.length() && s.charAt(i + j) == p.charAt(j)) j++;
5        if (j == p.length()) return i;                         // all characters matched
6    }
7    return -1;                                                  // contains(p) is indexOf(p) >= 0
8}
9// startsWith checks only i = 0; endsWith checks only i = s.length() - p.length()

Live state

s.length()

p.length()

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L2	s.length()=9 p.length()=3	Try 7 alignments of p inside s. The first full match wins.
2	L4	i=0 j=0	'a' matches p[0].
3	L4	i=0 j=1	'b' matches p[1].
4	L4	i=0 j=2	'c' != 'd': this alignment fails.
5	L4	i=1 j=0	'b' != 'a': this alignment fails.
6	L4	i=2 j=0	'c' != 'a': this alignment fails.
7	L4	i=3 j=0	'a' matches p[0].
8	L4	i=3 j=1	'b' matches p[1].
9	L4	i=3 j=2	'c' != 'd': this alignment fails.
10	L4	i=4 j=0	'b' != 'a': this alignment fails.
11	L4	i=5 j=0	'c' != 'a': this alignment fails.
12	L4	i=6 j=0	'a' matches p[0].
13	L4	i=6 j=1	'b' matches p[1].
14	L4	i=6 j=2	'd' matches p[2].
15	L5	return=6	All 3 characters matched at i = 6: return 6.

9.02.8

Split

s.split(regex) breaks a string at each match of a regular expression and returns the tokens. Two rules cause surprises: trailing empty strings are removed unless you pass a negative limit (split(",", -1)), and a leading delimiter produces an empty first token. "\\s+" splits on runs of whitespace. The argument is a regex, so metacharacters such as . and | must be escaped.

Compare the three methods on a,b,,c,,.

Java

1String[] a = "a,b,,c,,".split(",");           // [a, b, , c]  (length 4)
2String[] b = "a,b,,c,,".split(",", -1);       // [a, b, , c, , ]  (length 6)
3String[] c = ",x,y".split(",");               // [, x, y]
4String[] d = "a.b.c".split("\\.");             // escape the dot: [a, b, c]
5String[] w = "  go  to".trim().split("\\s+"); // [go, to]

split: how a string becomes tokens

Interactive · edit the input

char[] s · length 8

01234567

ReadingDelimiterPart of a token

tokens

none yet

Setup

Every comma ends a token. Two commas in a row make an empty token.

Step 1 / 11

Java

1static List<String> split(String s, char delim) {
2    List<String> out = new ArrayList<>();
3    StringBuilder cur = new StringBuilder();
4    for (char c : s.toCharArray()) {
5        if (c == delim) { out.add(cur.toString()); cur.setLength(0); }   // delimiter: close the token
6        else cur.append(c);
7    }
8    out.add(cur.toString());                      // the last token, possibly empty
9    return out;                                    // String.split(regex) then drops trailing empty tokens
10}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L2		Every comma ends a token. Two commas in a row make an empty token.
2	L6	i=0 current="a"	Append 'a' to the current token.
3	L5	i=1 token="a"	Delimiter: close the token "a".
4	L6	i=2 current="b"	Append 'b' to the current token.
5	L5	i=3 token="b"	Delimiter: close the token "b".
6	L5	i=4 token=""	Delimiter with nothing before it: an empty token is added.
7	L6	i=5 current="c"	Append 'c' to the current token.
8	L5	i=6 token="c"	Delimiter: close the token "c".
9	L5	i=7 token=""	Delimiter with nothing before it: an empty token is added.
10	L8	token=""	End of input: add the last token "" (empty).
11	L9	return=["a", "b", "", "c"] length=4	Java's split removes trailing empty tokens (but keeps leading and inner ones): 4 tokens.

9.02.9

Join

String.join(delimiter, parts) is the inverse of split: it inserts the delimiter between elements and none at the ends. It accepts varargs or any Iterable<? extends CharSequence>. For non-string items map them first, for example with Collectors.joining.

It builds the result in one allocation, so it is O(total length).

Java

1String s = String.join(", ", "a", "b", "c");                  // "a, b, c"
2String t = String.join("-", List.of("x", "y"));               // "x-y"
3String u = IntStream.of(3, 1, 2).mapToObj(String::valueOf).collect(Collectors.joining(" "));   // "3 1 2"

9.02.10

Comparison

equals compares content, equalsIgnoreCase ignores case, and compareTo orders lexicographically by UTF-16 units: it returns a negative number, 0 or a positive number, and only the sign is reliable. == compares references and should not be used for text.

Step through compareTo to see where the first difference is found.

Java

1boolean e = "Java".equals("java");               // false
2boolean ei = "Java".equalsIgnoreCase("java");    // true
3int c1 = "apple".compareTo("apricot");           // negative: 'p' (112) < 'r' (114) at index 2
4int c2 = "java".compareTo("javascript");         // -6: shorter string, length difference

compareTo and common prefix

Interactive · edit the input

char[] a · length 5

01234

ComparingEqual so farFirst difference

Setup

Compare character by character over the shorter length (5); the first difference decides.

Step 1 / 5

Java

1static int compareTo(String a, String b) {
2    int lim = Math.min(a.length(), b.length());
3    for (int k = 0; k < lim; k++) {
4        char x = a.charAt(k), y = b.charAt(k);
5        if (x != y) return x - y;                    // difference of the two code units
6    }
7    return a.length() - b.length();                  // one string is a prefix of the other
8}
9static int commonPrefix(String a, String b) {
10    int k = 0;
11    while (k < a.length() && k < b.length() && a.charAt(k) == b.charAt(k)) k++;
12    return k;
13}

Live state

a.length()

b.length()

lim

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L2	a.length()=5 b.length()=7 lim=5	Compare character by character over the shorter length (5); the first difference decides.
2	L5	k=0 x='a' (97) y='a' (97)	'a' equals 'a'.
3	L5	k=1 x='p' (112) y='p' (112)	'p' equals 'p'.
4	L5	k=2 x='p' (112) y='r' (114)	'p' (112) differs from 'r' (114).
5	L5	return=-2	Return 112 - 114 = -2: a sorts before b. Only the sign is guaranteed; do not rely on the magnitude.

9.02.11

Trimming

trim() removes leading and trailing characters whose code is at most U+0020 (spaces, tabs, newlines). strip() (Java 11) removes Unicode whitespace and is usually what you want; stripLeading and stripTrailing do one side. They return a new string, or the same one if nothing changed. Neither touches whitespace inside the text.

Trim input lines before parsing numbers.

Java

1String a = "  hi  ".trim();             // "hi"
2String b = "\u2003hi\u2003".strip();   // "hi": strip handles Unicode spaces, trim does not
3int n = Integer.parseInt(" 42 ".trim()); // 42; parseInt(" 42 ") would throw
4String c = "a b".strip();              // "a b": inner space is kept

Practice ladder

Now try it yourself

Easy

Extract "gori" from "algorithm" with substring
What does "abc".substring(3) return?

Medium

Predict the lengths of "a,b,,".split(",") and "a,b,,".split(",", -1)
Check if a file name ends with .java, ignoring case

Advanced

Implement your own split on a single character and compare it with String.split

Key takeaways

length, charAt are O(1); substring and indexOf copy or scan.
split removes trailing empty tokens unless the limit is negative; its argument is a regex.
Use equals for content and compareTo for ordering; trim() and strip() differ on Unicode spaces.