Skip to content
HopperHopper

Course navigation

For teachersTopic 2.10 · Lesson kit

Implementing String Algorithms

  • 3 class periods
  • 45 minutes each
  • Objective 2.10.A
  • 6 downloads with keys

Downloads

At a glance

Pacing
3 class periods of 45 minutes
Learning objectives
2.10.A
Essential knowledge
2.10.A.1
Materials
Projector and the Letter by Letter slide deckWhiteboard and markersMini whiteboards or scrap paperIDE on every computer (Days 1 and 3)Printed Letter by Letter puzzle worksheet (answer key for you) and exit ticket

45 minutes a day

Agenda

Day 145 minutes

  • Warm-up
  • Direct instruction
  • Guided practice
  • Closure
  • Activity
  1. 0:00–0:055 minWarm-updoes it have a digit? (slide 2)
  2. 0:05–0:2015 minDirect instructiontraversal with substring(i, i + 1) and the loop bound (slides 3–6)
  3. 0:20–0:255 minActivityDay 1 pause and try — hop, don't walk (slide 7)
  4. 0:25–0:4217 minGuided practicewalk strings in the IDE
  5. 0:42–0:453 minClosurewhich index is last?

Day 245 minutes

  • Warm-up
  • Direct instruction
  • Guided practice
  • Activity
  1. 0:00–0:055 minWarm-upsettle the digit question with a flag (slide 2)
  2. 0:05–0:2015 minDirect instructionany or every flags (slides 8–11)
  3. 0:20–0:3212 minDirect instructionlonger pieces and counting, overlaps (slides 12–13)
  4. 0:32–0:375 minActivityDay 2 pause and try — double letters (slide 14)
  5. 0:37–0:458 minGuided practicecount overlapping matches in the IDE

Day 345 minutes

  • Warm-up
  • Direct instruction
  • Guided practice
  • Closure
  • Exit ticket
  • Activity
  1. 0:00–0:055 minWarm-upwhat does += do to a string?
  2. 0:05–0:2015 minDirect instructionbuilding a new string and reversing (slides 15–18)
  3. 0:20–0:255 minActivityDay 3 pause and try — same backward? (slide 19)
  4. 0:25–0:3510 minGuided practicebuild the palindrome check in the IDE
  5. 0:35–0:405 minClosureflag, counter, or builder? (slides 20–21)
  6. 0:40–0:455 minExit ticket

Overview

This topic combines tools students already have: a loop and substring (Topics 1.15 and 2.8), a counter (2.9), and if with boolean expressions (2.3, 2.5). Day 1 is traversal: visit every character with substring(i, i + 1) and a correct bound. Day 2 is flags (does any character have a property, does every character) and looking at pieces longer than one character, including counting overlapping matches. Day 3 is building a new string with += and reversing a string, then choosing between a flag, a counter, and a builder (2.10.A.1).

Stay inside the boundary: no String methods beyond length, substring, indexOf, and equals, no arrays, no char. Compare strings with equals, never ==.

Teacher note

The slides are the Letter by Letter deck (21 slides); slide numbers refer to it. Day 1 uses slides 2–7, Day 2 slides 2 and 8–14, Day 3 slides 15–21. The worksheet (10 questions, about 35 minutes) is homework split by day: questions 2, 3, and 6 after Day 1; questions 1, 4, and 5 after Day 2; questions 7, 8, 9, and 10 after Day 3.

Demonstrations are in the topic’s examples/ folder (.snippet.java files hold only the statements for main): EachLetter, EveryOther, OneTooFar (Day 1); HasDigit, AllDigits, FlagReset, CountAa, CountAna, PairTooFar (Day 2); RemoveSpaces, ReversePrepend, ReverseBackward, BackwardTooFar, Palindrome (Day 3).

Day 1 · Warm-up: Does it have a digit?

Show slide 2 with the three passwords. Partners describe, step by step, how a program decides. Collect two ideas: look at one character at a time, and “yes” can be said as soon as one digit is found, while “no” needs every character checked. Keep the ideas on the board; Day 2 returns to them.

Day 1 · Direct instruction: Visit every character

Show slides 3 and 5. A loop from i = 0 while i < word.length() with word.substring(i, i + 1) visits each character once. Run EachLetter and point at the index row on slide 5. Then slide 6, the one step too far: <= makes one extra pass that asks for an index that does not exist.

Misconception: Looping up to length() with <=

The length is 5, so the last index “should” be 5. Indexes start at 0, so the last index is length() - 1. Run OneTooFar: it prints robin and then throws StringIndexOutOfBoundsException. Have students say the last index of “robin” aloud before they type a bound.

Day 1 pause and try

Slide 7: students write the output of the loop that steps by 2 and the indexes it visits (p, n, a, e; indexes 0, 2, 4, 6 of “pancake”, printing pnae). Reveal and check indexes, not just the output.

Day 1 · Guided practice: Guided practice

In the IDE, students write a traversal that prints each character on its own line, then change it to visit every other character (EveryOther), then deliberately write <= and read the exception message. Pairs explain which line of the message names the bad index.

Day 1 · Independent practice: Independent practice

Puzzle worksheet questions 2, 3, and 6 are homework: the hopping loop (JVM), the tile reverse of “stressed”, and the loop match-up.

Day 1 · Closure: Closure

Cold-call: “A string has length 8. What are the first and last index?” (0 and 7.)

Day 2 · Warm-up: Warm-up

Return to slide 2. Which passwords have a digit? (maple3leaf and R2D2; sunnyday does not.) Ask when the program can stop being unsure for “yes” versus “no”.

Day 2 · Direct instruction: Flags

Slide 9: a boolean hasDigit starts false, switches to true when a character matches, and is read only after the loop. Slide 10: for “every”, the flag starts true and switches to false on the first character that fails. Run HasDigit and AllDigits. Slide 11 shows the else that resets the flag.

Misconception: An else that resets the flag

“If digit, true; otherwise, false” looks tidy, but each pass overwrites the answer, so the flag describes only the last character. Run FlagReset with tiger7x: it prints Has a digit: false. Rule to teach: a flag changes once and never changes back.

Day 2 · Direct instruction: Longer pieces and counting

Slide 13: for pieces of length n, the loop runs while i <= length() - n, because substring(i, i + n) must stay inside the string. Checking every start counts overlapping matches: ahahaha has three aha. Run CountAna on “banana” (2 matches, starting at 1 and 3).

Misconception: Keeping the one-character bound

Copying the Day 1 header for two- or three-character pieces crashes at the last starts. Ask: “What is the last start index for 3-character pieces in a string of length 7?” (4.) Run PairTooFar.

Day 2 pause and try

Slide 14: “bookkeeper” has three double letters (oo, kk, ee), starting at indexes 1, 3, and 5. Ask for the start indexes, and why the loop stops at length() - 1.

Day 2 · Guided practice: Guided practice

In the IDE, students count “aa” in several strings and then count “ana” in “banana” to confirm overlaps are found. Declare the counter before the loop (worksheet WATCH OUT after question 5).

Day 2 · Independent practice: Independent practice

Puzzle worksheet questions 1, 4, and 5 (the substring bounds table, the snippet pool for counting “la”, and the any/every flag face-off). Question 1 supports the length() - n rule; question 5 settles the flag rules.

Day 3 · Warm-up: Warm-up

On a whiteboard, students write what String s = ""; s += "a"; s += "b"; leaves in s, and whether an earlier string changed (it did not; the variable now refers to a new string).

Day 3 · Direct instruction: Building and reversing

Slide 16: start the result at "" before the loop, add pieces with +=, and the original never changes. Run RemoveSpaces. Slide 17: reverse by adding each character to the front while walking forward, or to the end while walking backward; run ReversePrepend and ReverseBackward. Slide 18: the backward loop runs from length() - 1 down to 0.

Misconception: Starting the backward loop at length()

The length feels like “the end”, but index length() does not exist. Run BackwardTooFar to see the exception. Also point out i > 0 stops one early and drops the first character.

Misconception: Not starting the result at an empty string

A String r; with no value cannot be used with += (the compiler reports the variable might not have been initialized). Worksheet question 7 snippet 1 shows this.

Day 3 pause and try

Slide 19: “parts” reversed is strap and equals gives false. Ask which word would print true and why (a palindrome such as “level”).

Day 3 · Guided practice: Guided practice

In the IDE, students write the palindrome check from Palindrome: remove the spaces with a builder, reverse with a second builder, then compare with equals. Anyone who writes == runs PalindromeBug to see false for a word that reads the same backward.

Day 3 · Independent practice: Independent practice

Puzzle worksheet questions 7, 8, 9, and 10 are homework (you’re the compiler, two truths and a lie, one-token fix, wrap-up).

Day 3 · Closure: Closure and exit ticket

Slide 20 (vocabulary), then slide 21: partners say which tool (flag, counter, or builder) each job needs. Give the exit ticket (about five minutes). Question 1 checks counting overlapping substrings, question 2 flag logic, and question 3 the backward loop bound (all 2.10.A.1). Re-teach the weakest at the start of Topic 2.11.

Exit ticket

Question 1 · Tracing

Write the exact output.

String word = "banana";
int count = 0;
for (int i = 0; i <= word.length() - 3; i++)
{
    if (word.substring(i, i + 3).equals("ana"))
    {
        count++;
    }
}
System.out.println("ana appears " + count + " times");
Open in IDE
Check your reasoning
ana appears 2 times

The loop checks starts 0 through 3 (i <= 6 - 3). substring(1, 4) is ana and substring(3, 6) is ana; the other starts give ban and nan. The two matches overlap at the middle a, and checking every start counts both. A complete answer has the count 2.

Question 2 · Multiple choice

The code below should say whether password contains a digit. What does it print?

String password = "tiger7x";
String digits = "0123456789";
boolean hasDigit = false;
for (int i = 0; i < password.length(); i++)
{
    String letter = password.substring(i, i + 1);
    if (digits.indexOf(letter) >= 0)
    {
        hasDigit = true;
    }
    else
    {
        hasDigit = false;
    }
}
System.out.println("Has a digit: " + hasDigit);
Open in IDE
  1. Has a digit: true
  2. Has a digit: false
  3. Nothing; it does not compile.
  4. It throws a StringIndexOutOfBoundsException.
Check your reasoning

B. The 7 sets the flag to true, but the else runs on the next character, x, and sets it back to false. The flag describes only the last character. A is what the code was meant to do. C is wrong because every statement is legal. D is wrong because i < length() keeps every index valid. Fix: delete the else.

Question 3 · Short answer

This code should print “drawer” backward. Does it compile? What happens when it runs, and how do you fix it?

String word = "drawer";
String reversed = "";
for (int i = word.length(); i >= 0; i--)
{
    reversed += word.substring(i, i + 1);
}
System.out.println(reversed);
Open in IDE
Check your reasoning

Model answer: It compiles. The loop starts at word.length(), which is 6, but the last index is 5, so substring(6, 7) throws a StringIndexOutOfBoundsException on the first pass. Fix: start at word.length() - 1.

A complete answer says it compiles, names the exception (or a run-time error on the first pass), and gives the start length() - 1.