Implementing String Algorithms: Study Guide (Computer Science A 2.10)

Strings as sequences you can loop over

A String is an ordered sequence of characters, and you have already used methods to ask about it. Now you will combine those methods with loops to write real algorithms. The four methods you need are all in the Java Quick Reference:

Method	What it returns
int length()	the number of characters
String substring(int from, int to)	the characters from index from up to, but not including, to
String substring(int from)	the characters from from to the end
int indexOf(String str)	the index of the first occurrence of str, or -1 if there is none
boolean equals(Object other)	true if the characters are the same
int compareTo(String other)	negative, zero or positive, by alphabetical order

A String has index values from 0 to one less than its length. Asking for a position outside that range causes a StringIndexOutOfBoundsException.

String s = "rainbow";
System.out.println(s.length());
System.out.println(s.substring(2, 5));
System.out.println(s.substring(3));
System.out.println(s.indexOf("bow"));
System.out.println(s.indexOf("z"));

Output:

7
inb
nbow
4
-1

Visiting every character

A single character at index i is the String s.substring(i, i + 1): from i up to, not including, i + 1. Looping i from 0 to s.length() - 1 visits them all.

String s = "rainbow";
for (int i = 0; i < s.length(); i++) {
    System.out.print(s.substring(i, i + 1) + "-");
}

Output:

r-a-i-n-b-o-w-

The boundary i < s.length() is exactly right. At i = 6 the call is substring(6, 7), which is allowed because the end index may equal the length. If the loop ran to i <= s.length(), then i = 7 would call substring(7, 8) and throw an exception.

The three standard string algorithms

1. Does the string have a property? Count characters that meet a criterion. This is the frequency pattern from Topic 2.9 with the characters as the “values”. To test membership in a set of letters, use indexOf on a String of those letters: a result of 0 or more means “found”.

2. Count substrings that meet a criterion. Slide a window of length k along the string. A window starting at index i is s.substring(i, i + k). The last window starts at s.length() - k, so the loop runs i <= s.length() - k.

3. Build a new string. Start with the empty string "" and add to it. Putting each new character on the front reverses the order.

public class StringTools {
    public static int countVowels(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            String letter = s.substring(i, i + 1);
            if ("aeiou".indexOf(letter) >= 0) {
                count++;
            }
        }
        return count;
    }

    public static String reverse(String s) {
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            result = s.substring(i, i + 1) + result;
        }
        return result;
    }

    public static boolean isPalindrome(String s) {
        return s.equals(reverse(s));
    }

    public static void main(String[] args) {
        System.out.println(countVowels("rainbow"));
        System.out.println(reverse("rainbow"));
        System.out.println(isPalindrome("racecar"));
        System.out.println(isPalindrome("rainbow"));
    }
}

Output:

3
wobniar
true
false

countVowels("rainbow") finds a, i and o: 3. In reverse, each pass puts the new letter before what has been built so far: “r”, “ar”, “iar”, “niar”, “bniar”, “obniar”, “wobniar”. A palindrome reads the same both ways, so the test is that the string equals its reverse. Notice that isPalindrome uses equals, not ==: the reverse is a new object, so == would compare references and be false.

Strings are immutable

A String object cannot be changed. Methods such as substring and the + operator return a new String and leave the original alone. So a call whose result is not stored has no effect on the variable:

String s = "cat";
s.substring(1);
String t = s.substring(1);
System.out.println(s + " " + t);

Output:

cat at

The first call computes “at” and throws it away. Only the second stores it in t. The loop that builds result works because each pass assigns the new, longer String back to result.

Out of range

Each of these throws StringIndexOutOfBoundsException:

String w = "banana";
String bad1 = w.substring(4, 7);
String bad2 = w.substring(7);
String bad3 = w.substring(-1, 2);

The String has length 6, so valid ends are at most 6, and valid starts are at least 0. substring(6) (start equal to the length) is allowed and returns the empty String, but substring(7) is not. When you write a window loop, always check the last window.

Comparing strings

equals tests whether two Strings have the same characters. compareTo orders them alphabetically: a negative result means the first String comes first, zero means they are equal, and a positive result means it comes later. Use the sign, not a particular value.

String a = "apple";
String b = "banana";
System.out.println(a.equals(b));
System.out.println(a.compareTo(b) < 0);
System.out.println(b.compareTo(a) > 0);
System.out.println(a.compareTo("apple") == 0);

Output:

false
true
true
true

Worked example 1: counting a letter and building a new string

Question. Write a method countLetter(String s, String letter) that counts the occurrences of a one-letter String, and a method removeLetter(String s, String letter) that returns s with that letter left out. Use them on “banana” with “a”.

public class LetterTools {
    public static int countLetter(String s, String letter) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.substring(i, i + 1).equals(letter)) {
                count++;
            }
        }
        return count;
    }

    public static String removeLetter(String s, String letter) {
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            String current = s.substring(i, i + 1);
            if (!current.equals(letter)) {
                result = result + current;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(countLetter("banana", "a"));
        System.out.println(removeLetter("banana", "a"));
    }
}

Output:

3
bnn

Trace for removeLetter("banana", "a").

i	current	is it “a”?	result after
0	b	no	b
1	a	yes	b
2	n	no	bn
3	a	yes	bn
4	n	no	bnn
5	a	yes	bnn

Check. “banana” has three a’s, so countLetter is 3, and removing them leaves b, n, n. The original s is unchanged, because the method builds a new String. This follows the “build a new string” pattern: the new letter goes on the end (result + current) to keep the original order.

Worked example 2: counting substrings with a window

Question. Write countSub(String s, String target) that counts how many times target occurs in s, allowing occurrences to overlap. Find countSub("banana", "ana").

Plan. The window has the length of target, which is k = target.length(). It starts at i, and s.substring(i, i + k) is the window. The last start is s.length() - k, so the loop test is i <= s.length() - k.

public class CountSub {
    public static int countSub(String s, String target) {
        int count = 0;
        int k = target.length();
        for (int i = 0; i <= s.length() - k; i++) {
            if (s.substring(i, i + k).equals(target)) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countSub("banana", "ana"));
        System.out.println(countSub("banana", "na"));
        System.out.println(countSub("banana", "x"));
    }
}

Output:

2
2
0

Trace for countSub("banana", "ana"). Here k = 3 and the loop runs for i from 0 to 6 - 3 = 3.

i	window substring(i, i + 3)	equals “ana”?	count
0	ban	no	0
1	ana	yes	1
2	nan	no	1
3	ana	yes	2

Check. The two occurrences, at indexes 1 and 3, overlap on the middle “a”. Note what happens with a wrong boundary. With i < s.length() - k the last window, at i = 3, would be missed and the answer would be 1. With i < s.length() the window at i = 4 would be substring(4, 7), which is out of range and throws an exception.

How this appears in exam questions

String algorithms in an exam use only the methods in the Java Quick Reference: length, substring (both forms), indexOf, equals and compareTo. To look at one character you write substring(i, i + 1), and to compare it you use equals. Two habits protect you from the most common lost marks. First, check the last index you use: for single characters the loop stops at length() - 1, and for a window of k characters it stops at length() - k. An index outside the String throws a StringIndexOutOfBoundsException, which an examiner will treat as a bug. Second, remember that a String cannot be changed: if the task says to produce a modified String, build a new one in a variable and return that variable. When a question gives you a precondition about the input, such as words separated by single spaces, you can rely on it.

Common misconceptions

• “substring(a, b) includes the character at index b.” It stops before b, so the length of the result is b - a.
• “The last index is length().” It is length() - 1. substring(length()) is the empty String, but substring(length(), length() + 1) is out of range.
• “== compares strings.” It compares references. Use equals.
• “s.substring(1); shortens s.” Strings are immutable: the result must be assigned.
• “The window loop can run to length().” Each window must fit inside the String, so the last start is length() - k.
• “indexOf returns true or false.” It returns an index, with -1 for not found. Test with >= 0.
• “Building a new string in a loop changes the original.” The original is untouched; only the variable holding the result changes.

Where this leads

String algorithms use the same patterns as Topic 2.9: counting, searching and building. In Unit 4 the same ideas apply to arrays and ArrayList objects, and the searching and sorting algorithms of Topics 4.14 and 4.15 use compareTo on strings. Try the practice questions, recap with the revision notes and tick off the checklist. Then read the Topic 2.11 study guide on nested iteration. For the loop patterns, revisit the Topic 2.9 study guide.