AP Computer Science A · Unit 2 lecture · Part 9 of 12 · 9 min

2.10 Implementing String algorithmsWalking through a String

Mr. Thompkins
Combine a for loop with substring and you can do almost anything to a String: count letters, reverse it, find patterns. This is the heart of FRQ Question 1, part B.

The standard traversal visits every index once: for (int i = 0; i < s.length(); i++), and inside, String ch = s.substring(i, i + 1); is the character at index i, as a one-letter String. Compare it with equals, count it, or glue it onto a new String. Because Strings are immutable, "changing" a String always means building a new one, usually starting from the empty String "".

?Wait, why substring(i, i + 1) and not just one index?
substring(a, b) takes characters from a up to, not including, b. From i to i + 1 is exactly one character, the one at index i. The Quick Reference has no method that returns a single character as a String, so this is the AP way to get one.
1String w = "loop";2String rev = "";3int os = 0;4for (int i = 0; i < w.length(); i++)15{6    String ch = w.substring(i, i + 1);27    rev = ch + rev;38    if (ch.equals("o"))49    {10        os++;11    }12}13System.out.println(rev + " " + os);
  1. line 4 i goes 0 to length() - 1: every index once
  2. line 6 The character at index i, as a String
  3. line 7 Glue each new character on the front
  4. line 8 Compare Strings with equals
output › pool 2
Reversing a word and counting a letter in the same traversal, run under Java 17.
ichrev afteros after
0"l""l"0
1"o""ol"1
2"o""ool"2
3"p""pool"2
4stop: 4 < 4 is false
The trace for "loop". Gluing each character on the front builds the reverse.

To look at pieces longer than one character, slide a window: s.substring(i, i + k) is the k characters starting at i. The last legal start is s.length() - k, so the loop runs while i <= s.length() - k. Going one step further throws a StringIndexOutOfBoundsException.

1String s = "banana";2int count = 0;3for (int i = 0; i <= s.length() - 2; i++)14{5    if (s.substring(i, i + 2).equals("an"))26    {7        count++;8    }9}10System.out.println(count);
  1. line 3 A 2-letter window: the last start is length() - 2
  2. line 5 Look at characters i and i + 1 together
output › 2
Counting "an" in "banana" with a 2-letter window. The windows are ba, an, na, an, na. Run under Java 17.

indexOf gives a second way to find things. s.indexOf(t) is the first place t starts, or -1. To find every occurrence, find one, then keep only the part of the String after it and search again, until indexOf returns -1. Testing membership is another neat trick: "aeiou".indexOf(ch) is -1 exactly when ch is not a lowercase vowel.

?Wait, what does indexOf return when it finds nothing?
-1. Every real index is 0 or more, so -1 can't be confused with a position. That's why tests like s.indexOf("x") >= 0 (found) and s.indexOf("x") == -1 (not found) are so common.
Pause and think
A loop runs for (int i = 0; i <= s.length(); i++) and calls s.substring(i, i + 1). What happens on the last pass?
I thought about it. Show me
On the last pass, i equals s.length(), so substring(i, i + 1) asks for an end index of length() + 1, past the end of the String. It throws a StringIndexOutOfBoundsException. The loop condition should be i < s.length().
Count double letters
Write a static method doubleLetters(String s) that returns how many times a character is immediately followed by the same character. doubleLetters("bookkeeper") returns 3 (oo, kk, ee), and doubleLetters("aaa") returns 2.
  1. Pattern: count, over a 2-character window. Start with int count = 0;.
  2. Each pair compares index i with index i + 1, so the last i is s.length() - 2. Loop: for (int i = 0; i < s.length() - 1; i++).
    Why?
    i + 1 must still be a legal index. With i < s.length(), the last pass would ask for index length(), which doesn't exist.
  3. Inside: String a = s.substring(i, i + 1); and String b = s.substring(i + 1, i + 2);. If a.equals(b), count++.
    Why?
    Use equals, not ==, to compare Strings.
  4. After the loop, return count;. Check "aaa": pairs at i = 0 and i = 1 both match, so 2. Check "": the loop runs while 0 < -1, which is false, so it returns 0 without crashing.

Answer:

public static int doubleLetters(String s)
{
    int count = 0;
    for (int i = 0; i < s.length() - 1; i++)
    {
        String a = s.substring(i, i + 1);
        String b = s.substring(i + 1, i + 2);
        if (a.equals(b))
        {
            count++;
        }
    }
    return count;
}

doubleLetters("bookkeeper") returns 3 and doubleLetters("aaa") returns 2 (checked under Java 17).

Stuck? Get a hint
  1. You compare each character with the next one. What's the last index that has a next one?
  2. Get both characters with substring(i, i + 1) and substring(i + 1, i + 2).
  3. Compare them with equals, and count the matches.
Check yourself
What is printed?
String word = "banana";
String out = "";
for (int i = 0; i < word.length(); i++)
{
    String ch = word.substring(i, i + 1);
    if (!ch.equals("a"))
    {
        out += ch;
    }
}
System.out.println(out);
  1. Abnn
  2. Baaa
  3. Cbnna
  4. Dnnb
Show the answer

A. The loop keeps every character that isn't "a": b (index 0), n (2) and n (4), giving "bnn". Choice B is the opposite test. Choice C keeps the last a, but every "a" fails the test, including the one at the end.

  • Traverse with for (int i = 0; i < s.length(); i++) and s.substring(i, i + 1).
  • Build new Strings from "", gluing with +. Glue on the front to reverse.
  • A k-letter window: substring(i, i + k), with i <= s.length() - k.
  • indexOf finds the first match or -1; "aeiou".indexOf(ch) == -1 tests "not a vowel".