1. LxD Cycle Process

Empathize: Students write traversals that run one position too far and crash, because the last valid index is one less than the length and that gap is easy to forget.

Define:

  • POV: CSA students need to set loop bounds from length() deliberately, because an out of bounds traversal fails at run time rather than at compile time.
  • Learning Goal: Students will traverse Strings with a loop, take one character windows with substring, build new Strings, and set bounds that stay inside the String.

Ideate:

  • HMW Question: How might we make the boundary between the last valid index and the crash visible before students hit it?
  • Activity: A reverse-a-String walkthrough, a bounds and bugs activity, and a count-the-passes exercise.

Prototype & Test: Activity 3 is built around bounds specifically, because the out of bounds error is the failure that this topic produces most often.

2. 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 (5 minutes)

A String traversal is a for loop over the positions of the String.

  • length() gives the number of characters. Valid positions run from 0 to length() - 1.
  • substring(i, i + 1) takes the single character at position i.
  • Build a new String by starting with "" and concatenating inside the loop.
  • Going past length() - 1 throws StringIndexOutOfBoundsException, which is the most common runtime error in this topic.

3. Reference Guide

Key Ideas

  • A String has positions (indexes) from 0 to length() - 1.
  • s.substring(i, i + 1) is the single character at index i. Traverse a String with a for loop over i.
  • s.substring(i, i + k) is a window of k characters starting at i. The window must fit: i + k <= s.length(), so loop while i <= 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.

4. 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.

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);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

5. Hacks & Practice Tasks

Prepare your submission IPYNB

  1. Create a new notebook in your portfolio homework area: _notebooks/homework.
  2. Add one markdown cell at the top with the frontmatter:
---
layout: post
title: CSA Unit 2.10 Implementing String Algorithms HW
categories: [Java, String-Algorithms]
lesson_language: Java
lesson_topic: String-Algorithms HW
lesson_source: APCSA
lesson_type: lesson
permalink: /csa/unit_02/2_10_hw
author: yourGithubID
---
  1. Add code cells for the Popcorn Hack and the Homework Hack. Ensure all code runs and output is visible.
  2. Include a markdown cell before each code section explaining the concept.

Submission Safety Rules (Read First)

[IMPORTANT] To avoid grading errors, follow these rules exactly:

  • Write your prediction before you run each code section
  • Execute every code cell and leave the output visible
  • Show your work for any hand-traced prediction
  • Do not just copy code; explain what each line does
  • Label each question clearly

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.

Find a Substring
Blue letters are inside the current window.

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.

Reverse with a Loop
Each pass reads one character with substring(i, i + 1).

Activity 3: Bounds and Bugs

Bounds and Bugs
Off by one errors are the most common String mistake on the exam.
Question 1

What does this print?

String s = "program";
System.out.println(s.substring(3, 6));
Question 2

word is "iterate" and sub is "rate". What happens?

for (int i = 0; i < word.length(); i++) {
String window = word.substring(i, i + sub.length());
if (window.equals(sub)) {
System.out.println("found at " + i);
}
}
Question 3

Which loop counts how many times the letter a appears in s?

Activity 4: Count the Passes

Window Math
Type a number or a String.
Question 1

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?

Question 2

What is "computer".substring(3, 6)? Type the characters only.

Popcorn Hack (In-Class)

Count the vowels in word. Use a one character window and a compound Boolean expression with ||. Expected for iterate: 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);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Homework Hack

Two short tasks.

  1. Finish the runner: isPalindrome returns true when a String reads the same backwards. Build the reversed String, then compare with .equals.
  2. Answer the quick check.

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);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...
Homework Quick Check
Type the output exactly.

What does this print?

String s = "loop";
String out = "";
for (int i = 0; i < s.length(); i += 2) {
out += s.substring(i, i + 1);
}
System.out.println(out);

6. Grading Plan (1 Point Total)

Classroom Rubric

  • 0.2 points: Popcorn completion Student counted the vowels in word using a one character window and a compound condition with ||, printing 4 for iterate.

  • 0.8 points: Homework completion

    • 0.5 Palindrome: isPalindrome builds the reversed String and compares with .equals, returning correct results for a palindrome and a non-palindrome.
    • 0.2 Quick check: The traversal question is answered with the index range stated.
    • 0.1 Notebook quality: Every code cell executed with output visible, and a markdown cell before each code section explaining the concept.

Quick Validation Checklist

  • Present: loop bound derived from length()
  • Present: .equals used for the String comparison
  • Absent: any index that can reach length()
  • Test: iterate yields 4 vowels; racecar is a palindrome and java is not

7. Lesson Revisions & Feedback Evidence

Feedback Received: Team review of the Unit 2 set found that these lessons did not follow the section format used by the Unit 1 lessons, and that they ended without the assignment submission form every other CSA lesson provides.

Revision Made: The lesson was reorganised into the shared CSA lesson format, so it now opens with the LxD cycle and lesson plan, states its reference material before the code, and groups the activities, Popcorn Hack and Homework Hack under one practice section. The duplicate lesson heading was removed, and the page now renders the standard Submit Assignment form at the end.

Design Decision Kept: Activity 3 is built around bounds specifically, because the out of bounds error is the failure that this topic produces most often.

Open Item: Record peer feedback from the team teach delivery here once the lesson has been taught.

8. Summary

  • Traverse with for (int i = 0; i < s.length(); i++) and substring(i, i + 1).
  • A window of length k needs i <= s.length() - k.
  • .equals for comparisons, + to build new Strings.
  • Reverse by putting each new character in front; palindrome means rev.equals(s).
  • Next lesson: loops inside loops.

9. References

College Board Course and Exam Description

Topic 2.10, Implementing String Algorithms, is required content on the AP Computer Science A Exam. The objective quoted in section 2 of this lesson 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

Submit Assignment

Click to upload or drag and drop
PDF, ZIP, images, documents, or Jupyter notebooks (.ipynb) (Max 10MB per file)

Need to update a submission later? Open the submissions dashboard.