2.10 Implementing String Algorithms
Traverse a String with a loop and substring to search, count, reverse, and build new Strings.
- Reference Guide
- College Board Requirements
- Lesson Plan
- Code Examples
- A. Simple: String Algorithms in Code
- Code Runner Challenge
- Hacks & Practice Tasks
- Activity 1: Sliding Window Search
- Activity 2: Reverse a String
- Activity 3: Bounds and Bugs
- Activity 4: Count the Passes
- Popcorn Hack
- Code Runner Challenge
- Homework Hack
- Code Runner Challenge
- References
Reference Guide
Key Ideas
- A String has positions (indexes) from
0tolength() - 1. s.substring(i, i + 1)is the single character at indexi. Traverse a String with aforloop overi.s.substring(i, i + k)is a window ofkcharacters starting ati. The window must fit:i + k <= s.length(), so loop whilei <= s.length() - k.- Compare Strings with
.equals, never==. - Build a new String by starting with
""and adding pieces with+. - Standard algorithms: count a character, find or count a substring, reverse, check a palindrome.
Methods You Will Use
| Method | Meaning | Example (s = "iterate") |
|---|---|---|
s.length() |
number of characters | 7 |
s.substring(2, 5) |
characters at 2, 3, 4 (stops before 5) | "era" |
s.substring(4) |
from index 4 to the end | "ate" |
s.indexOf("ra") |
index of the first match, or -1 | 3 |
s.equals(t) |
same characters? | true or false |
- Going past the end throws a
StringIndexOutOfBoundsException. Check the loop bounds first.
College Board Requirements
AP CSA Unit 2, Topic 2.10: Implementing String Algorithms.
This lesson is built directly against the College Board’s stated learning objective for this topic:
Develop algorithms that traverse String objects.
Topic 2.10, Implementing String Algorithms, is required content on the AP Computer Science A Exam. The learning objective quoted above is the College Board’s own wording for this topic, and the activities, Popcorn Hack and Homework Hack are all written against it.
Lesson Plan
Learning Objective: Develop algorithms that traverse String objects.
Success Criteria: You can traverse a String with a loop, use substring to take a one character window, and build a new String without running past either end.
Tech Talk & Introduction
A String traversal is a for loop over the positions of the String.
length()gives the number of characters. Valid positions run from0tolength() - 1.substring(i, i + 1)takes the single character at positioni.- Build a new String by starting with
""and concatenating inside the loop. - Going past
length() - 1throwsStringIndexOutOfBoundsException, which is the most common runtime error in this topic.
Code Examples
A. Simple: String Algorithms in Code
Run the program. Then change word and sub and confirm the search still finds matches at the very end of the String.
Sliding window search with correct bounds, plus counting a substring.
public class StringFinder {
public static void main(String[] args) {
String word = "iterate";
String sub = "rate";
boolean found = false;
// The window must fit, so the last start index is word.length() - sub.length()
for (int i = 0; i <= word.length() - sub.length(); i++) {
String window = word.substring(i, i + sub.length());
if (window.equals(sub)) {
found = true;
System.out.println("Found \"" + sub + "\" at index " + i);
}
}
if (!found) {
System.out.println("\"" + sub + "\" is not in \"" + word + "\"");
}
// Count how many windows of length 2 appear in the word
int count = 0;
String pair = "te";
for (int i = 0; i <= word.length() - pair.length(); i++) {
if (word.substring(i, i + pair.length()).equals(pair)) {
count++;
}
}
System.out.println("\"" + pair + "\" appears " + count + " times");
}
}
Code Runner Challenge
Sliding window search with correct bounds, plus counting a substring.
View IPYNB Source
// CODE_RUNNER: Sliding window search with correct bounds, plus counting a substring.
public class StringFinder {
public static void main(String[] args) {
String word = "iterate";
String sub = "rate";
boolean found = false;
// The window must fit, so the last start index is word.length() - sub.length()
for (int i = 0; i <= word.length() - sub.length(); i++) {
String window = word.substring(i, i + sub.length());
if (window.equals(sub)) {
found = true;
System.out.println("Found \"" + sub + "\" at index " + i);
}
}
if (!found) {
System.out.println("\"" + sub + "\" is not in \"" + word + "\"");
}
// Count how many windows of length 2 appear in the word
int count = 0;
String pair = "te";
for (int i = 0; i <= word.length() - pair.length(); i++) {
if (word.substring(i, i + pair.length()).equals(pair)) {
count++;
}
}
System.out.println("\"" + pair + "\" appears " + count + " times");
}
}
StringFinder.main(null);
Hacks & Practice Tasks
Activity 1: Sliding Window Search
The window is the same length as sub. It slides one index at a time and stops when it can no longer fit. Try sub = ate to see a match at the very end, and sub = xyz for no match.
Activity 2: Reverse a String
Build a new String one character at a time. Notice the new character goes in front of what was built so far.
Activity 3: Bounds and Bugs
What does this print?
word is "iterate" and sub is "rate". What happens?
Which loop counts how many times the letter a appears in s?
Activity 4: Count the Passes
word.length() is 7 and sub.length() is 3. How many times does the body of for (int i = 0; i <= word.length() - sub.length(); i++) run?
What is "computer".substring(3, 6)? Type the characters only.
Popcorn Hack
Count the vowels in word. Use a one character window and a compound Boolean expression with ||. Expected for iterate: 4.
Popcorn hack: count vowels with substring and
public class VowelCounter {
public static void main(String[] args) {
String word = "iterate";
int vowels = 0;
// TODO: for each index i, take word.substring(i, i + 1)
// and count it if it equals a, e, i, o, or u
System.out.println("Vowels: " + vowels); // expected: 4
}
}
Code Runner Challenge
Popcorn hack: count vowels with substring and
View IPYNB Source
// CODE_RUNNER: Popcorn hack: count vowels with substring and ||. Expected: 4.
public class VowelCounter {
public static void main(String[] args) {
String word = "iterate";
int vowels = 0;
// TODO: for each index i, take word.substring(i, i + 1)
// and count it if it equals a, e, i, o, or u
System.out.println("Vowels: " + vowels); // expected: 4
}
}
VowelCounter.main(null);
Homework Hack
Two short tasks.
- Finish the runner:
isPalindromereturnstruewhen a String reads the same backwards. Build the reversed String, then compare with.equals. - Answer the quick check.
Homework: palindrome check with a reversed String and equals.
public class Palindrome {
public static boolean isPalindrome(String s) {
String rev = "";
// TODO: build rev by adding each character to the front
// TODO: return whether rev equals s
return false;
}
public static void main(String[] args) {
System.out.println("racecar: " + isPalindrome("racecar")); // true
System.out.println("level: " + isPalindrome("level")); // true
System.out.println("java: " + isPalindrome("java")); // false
}
}
Code Runner Challenge
Homework: palindrome check with a reversed String and equals.
View IPYNB Source
// CODE_RUNNER: Homework: palindrome check with a reversed String and equals.
public class Palindrome {
public static boolean isPalindrome(String s) {
String rev = "";
// TODO: build rev by adding each character to the front
// TODO: return whether rev equals s
return false;
}
public static void main(String[] args) {
System.out.println("racecar: " + isPalindrome("racecar")); // true
System.out.println("level: " + isPalindrome("level")); // true
System.out.println("java: " + isPalindrome("java")); // false
}
}
Palindrome.main(null);
What does this print?
References
College Board Course and Exam Description
Topic 2.10, Implementing String Algorithms, is required content on the AP Computer Science A Exam. The learning objective quoted in section 3 (College Board Requirements) is the College Board’s own wording for this topic, and the activities, Popcorn Hack and Homework Hack are all written against it.
Outside Academic Reference
String positions are zero-based and substring takes a start index and an exclusive end index, which is why a one character window is written as substring(i, i + 1) and why the last valid start index is one less than the length.
Reference List
College Board. (2025). AP Computer Science A: Course and exam description. https://apcentral.collegeboard.org/courses/ap-computer-science-a
Gosling, J., Joy, B., Steele, G., Bracha, G., Buckley, A., Smith, D., & Bierman, G. (2023). The Java language specification: Java SE 21 edition. Oracle America. https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/lang/String.html