Historical Context & Motivation
Text processing is one of the oldest problems in computing. Long before graphical interfaces existed, programmers manipulated strings—sequences of characters—to parse commands, search documents, and validate data. Every modern application, from search engines to DNA sequence analysis, relies on efficient string algorithms. Understanding how selection and iteration combine to traverse and transform strings is therefore foundational to computer science, and it occupies a prominent place on the AP Computer Science A exam.
The central question this lesson addresses is: how do you combine for/while loops with if/else decisions and Java's String methods to solve problems like counting characters, reversing text, checking for palindromes, and searching for substrings—all patterns that appear frequently on the AP exam?
Core Principles & Definitions
Before writing any algorithm, you must internalize a few facts about Java strings. A String is an immutable sequence of char values indexed from 0 to length() - 1. Because strings are immutable, every operation that appears to modify a string actually returns a new String object. This immutability shapes every algorithm you write: you traverse with an index variable, read characters with charAt(i) or extract pieces with substring(start, end), and build results by concatenating onto an accumulator.
Immutability
toUpperCase() return a new String; the original is unaffected.Zero-Based Indexing
Traversal via Iteration
for loop from 0 to str.length() (exclusive) to visit each character exactly once—the standard traversal pattern.Selection Inside Traversal
if statements inside the loop body to filter, count, or transform only characters that meet a condition.Accumulator Pattern
Visual Explanation — String Traversal
The diagram above illustrates the canonical traverse-and-accumulate pattern. The loop variable i advances from 0 through str.length() - 1. At each step, charAt(i) retrieves the current character, the if statement decides whether it is a vowel, and the accumulator count is incremented only when the condition is true. This same skeleton applies whether you are counting uppercase letters, replacing characters, or building a reversed copy of the string—only the condition and the accumulator type change.
How It Works — Key String Methods & Patterns
Essential String Methods for the AP Exam
| Method | Return Type | Description |
|---|---|---|
length() | int | Returns the number of characters in the string. |
charAt(int i) | char | Returns the character at index i. Throws StringIndexOutOfBoundsException if i < 0 or i ≥ length(). |
substring(int a, int b) | String | Returns the substring from index a (inclusive) to b (exclusive). |
indexOf(String s) | int | Returns the index of the first occurrence of s, or −1 if not found. |
equals(String s) | boolean | Returns true if strings have the same character sequence. Always use equals, never == for content comparison. |
compareTo(String s) | int | Returns negative, zero, or positive int based on lexicographic ordering. |
Pattern: Forward Traversal with Accumulator
str.length() − 1. The loop body applies selection (if/else) to each character and updates an accumulator.Pattern: Reverse Traversal
Pattern: Substring Window
i <= str.length() - target.length() prevents extracting a substring that extends past the end. This counts all (possibly overlapping) occurrences of target.Classic String Algorithms in Detail
Several classic string tasks recur on the AP exam and in introductory CS courses. Each is a variation of the traverse-and-accumulate skeleton, differing in the type of accumulator and the selection logic. The diagram below maps five common algorithms to their accumulator type and loop direction, making it easy to see their structural similarities.
Notice that every algorithm in the diagram uses the same three-part structure: a loop that walks through the string, a conditional that decides what happens with each character or substring, and an accumulator that gathers the result. For counting tasks, the accumulator is an int; for building a new string, it is a String initialized to ""; for yes/no decisions like palindrome checks, it is a boolean. Mastering this skeleton means you can solve almost any string problem on the AP exam by simply plugging in the right accumulator type and condition.
Worked Example — Palindrome Checker
Write a method isPalindrome(String s) that returns true if the string reads the same forwards and backwards (case-sensitive), and false otherwise. For example, isPalindrome("racecar") returns true, while isPalindrome("hello") returns false.
boolean. We can either start optimistic (true) and set it to false upon a mismatch, or build a reversed string and compare. The first approach is more efficient—O(n/2).i = 0 to i < s.length() / 2. Integer division handles both even- and odd-length strings correctly (the middle character of an odd-length string does not need comparison).s.charAt(i) with s.charAt(s.length() - 1 - i). If they differ, the string is not a palindrome, so we immediately return false.true.public static boolean isPalindrome(String s) {
for (int i = 0; i < s.length() / 2; i++) {
if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
return false;
}
}
return true;
}Strengths, Limitations & Trade-offs
Different string algorithm strategies have different performance and readability characteristics. The table below compares three common approaches you might consider when solving string problems on the AP exam.
| Approach | Strengths | Limitations |
|---|---|---|
| charAt + for loop | Full control over index; supports forward, reverse, or skip-by-n traversal; no extra String objects created per character access. | Verbose; off-by-one errors are easy to introduce; requires manual index arithmetic. |
| substring + equals | Reads clearly when matching multi-character patterns; directly expresses intent. | Creates new String objects on each call, costing extra time and memory; loop bound must account for target length. |
| indexOf (library search) | Shortest code; handles edge cases internally; single method call for first occurrence. | Less transparent for learning; cannot easily count all overlapping occurrences; hides the algorithm. |
Connection to Advanced Topics
The string algorithms covered in AP CSA lay the groundwork for far more sophisticated techniques you will encounter in a college data structures or algorithms course. The table below previews how each AP-level concept extends into advanced territory.
| AP CSA Concept | Advanced Extension |
|---|---|
| charAt traversal with accumulator | StringBuilder for O(n) concatenation; char arrays for in-place mutation |
| Brute-force substring search O(n × m) | KMP, Rabin-Karp, and Boyer-Moore algorithms for O(n + m) search |
| Palindrome check via half-scan | Manacher's algorithm for finding all palindromic substrings in O(n) |
| String equality with .equals() | Hashing (String.hashCode()) and hash tables for O(1) average-case lookup |
| Lexicographic comparison with compareTo | Trie data structures for prefix-based search and autocomplete |
One critical efficiency lesson you will learn beyond the AP exam involves String concatenation inside loops. Because Java strings are immutable, each result += ch creates a new String object, making an apparently O(n) loop actually O(n²) in terms of character copies. The StringBuilder class, which is not tested on the AP exam, solves this by providing a mutable buffer that appends characters in amortized O(1) time. Awareness of this trade-off is a bridge between AP CSA and real-world Java programming.
Practice Problems
String s = "COMPUTER";
int count = 0;
for (int i = 0; i < s.length(); i++) {
if ("AEIOU".indexOf(s.charAt(i)) >= 0) {
count++;
}
}
System.out.println(count);
What is printed as a result of executing the code segment?result after the following code executes?
String str = "banana";
String result = "";
for (int i = str.length() - 1; i >= 0; i--) {
result += str.substring(i, i + 1);
}public static String mystery(String s) {
String r = "";
for (int i = 0; i < s.length(); i++) {
if (i % 2 == 0) {
r += s.substring(i, i + 1);
}
}
return r;
}
What does mystery("ABCDEFGH") return?public static int countSubstring(String str, String target) that returns the number of times target appears as a (possibly overlapping) substring in str. For example, countSubstring("aaaa", "aa") returns 3 (positions 0, 1, and 2).
(a) Write the complete method.
(b) Trace through the execution for countSubstring("abcabc", "abc").public static String removeChar(String s, char ch) {
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ch) {
s = s.substring(0, i) + s.substring(i + 1);
}
}
return s;
}
(a) Explain why removeChar("aab", 'a') does NOT return "b".
(b) Identify the bug and provide a corrected version.
(c) Explain the time complexity of the corrected version.