Topic 2.10 Notes – Implementing String Algorithms

1. What String Algorithms Are

A string algorithm is just a systematic way to process text.

Remember:

• A String is a sequence of characters.
• Indices start at 0.
• Strings are immutable. You can’t change characters in place. Any “change” creates a new string.

Core tools you already know:

• length() → number of characters
• charAt(i) → character at index i
• substring(start, end) → start inclusive, end exclusive
• equals() → compares contents (not ==)

On the AP exam, you’re usually asked to:

• Determine if substrings have a property
• Count substrings that meet criteria
• Create a new string, often reversed

Everything builds from clean index control.

2. Character by Character Processing

Most string algorithms start by traversing one character at a time.

for (int i = 0; i < str.length(); i++) {
    char ch = str.charAt(i);
    // process ch
}

Strings in Java are indexed starting at 0 from left to right, so the first character is at index 0 and the last character is at str.length() - 1.

Checking a Property

You often test whether a string satisfies some condition.

Common patterns:

• “At least one” case
  Return true as soon as you find it.
• “All characters” case
  Return false as soon as one violates the rule.

Example: check if all characters are lowercase.

for (int i = 0; i < str.length(); i++) {
    char ch = str.charAt(i);
    if (ch < 'a' || ch > 'z') {
        return false;
    }
}
return true;

Early returns are expected on FRQs. Don’t overcomplicate them.

Counting Matches

Use an accumulator variable.

int count = 0;

for (int i = 0; i < str.length(); i++) {
    if (str.charAt(i) == 'x') {
        count++;
    }
}
return count;

This pattern appears constantly in quizzes and MCQs where you trace how many times count increases.

Be careful about:

• Case sensitivity
• Starting and ending loop bounds

3. Substring Processing and Pattern Counting

Now instead of single characters, you examine chunks.

How Substring Bounds Work

substring(start, end) includes start, excludes end.

If you want all substrings of length k, the last valid starting index is:

str.length() - k

So the loop condition must be:

for (int i = 0; i <= str.length() - k; i++) {
    String sub = str.substring(i, i + k);
}

Think of this like a sliding window of size k moving across the string. Each position of the window represents one substring of length k.

Sliding window of size 3 across a string

Notice how the window starts at the left and shifts one position at a time until it reaches the last valid group of three characters.

That <= is intentional here. This is where students lose points.

Counting Substrings That Meet Criteria

General structure:

1. Determine substring length (or rule).
2. Loop over valid starting indices.
3. Extract substring.
4. Check condition.
5. Increment counter.

Example: count occurrences of "cat".

int count = 0;
int len = 3;

for (int i = 0; i <= str.length() - len; i++) {
    if (str.substring(i, i + len).equals("cat")) {
        count++;
    }
}
return count;

Use .equals() every time you compare strings.

A very common AP trick is overlapping matches. This loop correctly counts overlaps.

4. Building and Reversing Strings

Because strings are immutable, you build a new one using an accumulator.

String result = "";

for (int i = 0; i < str.length(); i++) {
    if (str.charAt(i) != ' ') {
        result += str.charAt(i);
    }
}
return result;

This pattern handles:

• Removing characters
• Replacing characters
• Extracting digits
• Applying simple ciphers

Reversing a String

Classic version:

String result = "";

for (int i = str.length() - 1; i >= 0; i--) {
    result += str.charAt(i);
}
return result;

Or for palindrome checks, compare front and back moving inward.

When you see a reverse FRQ, write it cleanly. No need for nested loops.

Common Mistakes That Cost Points

1. Off-by-one errors

Wrong:

i <= str.length()

Correct:

i < str.length()

Except in substring loops where <= length - k is required.

2. Using == instead of .equals()

This fails on the exam every year.

3. Forgetting end index is exclusive

To get 4 characters starting at i:

substring(i, i + 4)

4. Not handling short strings

If target length is 5 and string length is 3, your loop must not execute.
i <= str.length() - k naturally handles this if written correctly.