Difficulty: Intermediate | Prerequisites: Java String methods (indexOf, substring, length), class design basics, instance variables
This question comes from the 2017 AP Computer Science A free-response exam (Question 3). It tests your ability to manipulate strings inside a custom Java class, specifically finding and replacing substrings by their occurrence number. You need to be comfortable with indexOf, substring, and string concatenation before attempting this.
If you have not yet worked through basic String method problems, or if class design with instance variables and helper methods feels unfamiliar, start there first. This question builds directly on those foundations.
You are given a Phrase class that stores a string in an instance variable. You write two methods: replaceNthOccurrence (which swaps the nth occurrence of a substring with a replacement) and findLastOccurrence (which returns the index of the last occurrence of a substring). Both methods rely on a provided helper, findNthOccurrence, which you must call rather than reimplementing from scratch.
Phrase class
A custom Java class that wraps a single String (stored in currentPhrase) and provides methods for searching and modifying substrings within it. Think of it as a String with extra powers for finding and replacing by occurrence number.
currentPhrase
The private instance variable (a String) that holds the phrase being manipulated. All methods in the Phrase class read from or write to this variable.
findNthOccurrence(String str, int n)
A provided helper method that returns the index (position) of the nth occurrence of str inside currentPhrase. Returns -1 if the nth occurrence does not exist. In simple terms, it answers: "Where does the nth copy of this substring start?"
replaceNthOccurrence(String str, int n, String repl)
The method you write in Part (a). It finds the nth occurrence of str in currentPhrase and swaps it out for repl. If the nth occurrence does not exist, it leaves currentPhrase unchanged.
findLastOccurrence(String str)
The method you write in Part (b). It returns the index of the final (last) occurrence of str in currentPhrase. Returns -1 if str is not found at all. Think of it as asking: "Where does this substring appear for the very last time?"
Precondition
A stated assumption the method is allowed to rely on. Here, preconditions guarantee that str.length() > 0 and n > 0, so you do not need to handle empty strings or non-positive n values.
Postcondition
A guarantee about what is (or is not) changed after the method runs. findNthOccurrence and findLastOccurrence have the postcondition that currentPhrase is not modified.
The Phrase class has one private instance variable, currentPhrase, which holds the string being worked on. The constructor takes a String parameter and assigns it to currentPhrase. The class provides toString() to return currentPhrase and the helper method findNthOccurrence.
The key design pattern here is that the helper method does the hard searching work, and your job is to use it correctly. The AP exam rewards you for calling findNthOccurrence rather than reimplementing string-searching logic yourself.
Method signature: public void replaceNthOccurrence(String str, int n, String repl)
What it does: finds the nth occurrence of str in currentPhrase and replaces it with repl. If the nth occurrence does not exist, currentPhrase stays the same.
The approach:
Call findNthOccurrence(str, n) to get the starting index of the nth occurrence
If the index is -1, do nothing (the occurrence does not exist)
Otherwise, rebuild currentPhrase by concatenating three pieces: everything before the occurrence, the replacement string, and everything after the occurrence
Sample solution:
public void replaceNthOccurrence(String str, int n, String repl) {
int index = findNthOccurrence(str, n);
if (index != -1) {
currentPhrase = currentPhrase.substring(0, index)
+ repl
+ currentPhrase.substring(index + str.length());
}
}Trace through the examples:
"A cat ate late." replacing 1st "at" with "rane": findNthOccurrence returns index 3 (the "at" in "cat"). Result: "A crane ate late."
"A cat ate late." replacing 6th "at" with "xx": findNthOccurrence returns -1 (only 3 occurrences of "at" exist). Phrase unchanged.
"aaaa" replacing 1st "aa" with "xx": findNthOccurrence returns index 0. Result: "xxaa"
"aaaa" replacing 2nd "aa" with "bbb": findNthOccurrence returns index 2. Result: "aabbb" (but the exam shows "abbba", meaning the 2nd "aa" starts at index 1, which tells you findNthOccurrence counts non-overlapping occurrences starting fresh each time from after the previous match)
Method signature: public int findLastOccurrence(String str)
What it does: returns the index of the last occurrence of str in currentPhrase. Returns -1 if str is not found.
The approach:
You must use findNthOccurrence (required for full credit)
Call findNthOccurrence with increasing values of n until it returns -1
The last value that was not -1 is the index of the final occurrence
Sample solution:
public int findLastOccurrence(String str) {
int lastIndex = -1;
int n = 1;
int index = findNthOccurrence(str, n);
while (index != -1) {
lastIndex = index;
n++;
index = findNthOccurrence(str, n);
}
return lastIndex;
}Trace through the examples (using "A cat ate late."):
findLastOccurrence("at"): "at" appears at indices 3, 5, 11. Loop runs for n=1,2,3 (all valid), then n=4 returns -1. Returns 11.
findLastOccurrence("cat"): "cat" appears only at index 2. Loop runs for n=1 (valid), then n=2 returns -1. Returns 2.
findLastOccurrence("bat"): "bat" never appears. First call with n=1 returns -1. Returns -1.
Students often try to write their own loop to find the nth occurrence instead of calling findNthOccurrence. The exam explicitly requires you to use the helper method. Reimplementing the search logic will cost you points even if it produces correct output.
A common mistake in replaceNthOccurrence is using index + repl.length() instead of index + str.length() when calculating the "after" portion. You need to skip past the original substring (str), not the replacement (repl), because you are cutting out str from the original.
Students sometimes forget to handle the -1 case. If findNthOccurrence returns -1, you must leave currentPhrase unchanged. Attempting to call substring with -1 will cause a StringIndexOutOfBoundsException.
In findLastOccurrence, some students try a fixed upper bound for the loop (like n = 100) instead of looping until findNthOccurrence returns -1. The correct pattern is a while loop that keeps incrementing n until the helper signals there are no more occurrences.
This FRQ tests two skills the AP exam values highly: using a helper method correctly (rather than reinventing it) and precise String manipulation with substring and concatenation.
Part (a) is a classic "use the provided method" question. The rubric awards points specifically for calling findNthOccurrence. Writing your own search loop, even if correct, forfeits those points.
Part (b) tests the pattern of "keep going until you run out" using a while loop. This iterative search pattern appears frequently in AP CS A questions.
String index arithmetic is a perennial source of errors on the exam. Practise tracing through substring calls with concrete indices until the boundary calculations feel automatic.
The exam may present overlapping substring scenarios (like "aa" inside "aaaa"). Understanding how findNthOccurrence handles overlaps is worth thinking through, even though the method is provided.
True or False: replaceNthOccurrence should return the modified string. Answer: False. It is a void method that modifies currentPhrase directly.
Fill in the blank: If findNthOccurrence returns ______, replaceNthOccurrence should leave the phrase unchanged. Answer: -1
True or False: In findLastOccurrence, you should start with n = 0 and increment upwards. Answer: False. Occurrences are numbered starting at 1 (the precondition states n > 0).
Fill in the blank: To get the portion of currentPhrase after the matched substring, use currentPhrase.substring(index + ______). Answer: str.length()
True or False: findLastOccurrence modifies currentPhrase. Answer: False. Its postcondition states the phrase is not modified.
Q: Given Phrase p = new Phrase("the three trees");, what is the result of p.replaceNthOccurrence("the", 2, "a");?
A: "the three aes". The 2nd occurrence of "the" is inside "three" at index 4. It gets replaced with "a", producing "the ares". Wait, let us trace more carefully. "the three trees" has "the" at index 0, then "the" at index 10 (in "trees"). findNthOccurrence("the", 2) returns 10. The result is "the three es" with "a" inserted: "the three aes".
Q: Write the body of replaceNthOccurrence without looking at the solution. What are the three pieces you concatenate?
A: The part before the occurrence (currentPhrase.substring(0, index)), the replacement string (repl), and the part after the occurrence (currentPhrase.substring(index + str.length())).
Q: If findNthOccurrence("xyz", 1) returns -1, what should replaceNthOccurrence do?
A: Nothing. currentPhrase remains unchanged because the substring was not found.
Q: In findLastOccurrence, why do you need a separate variable to track the last valid index rather than just returning inside the loop?
A: Because you do not know an occurrence is the last one until the next call to findNthOccurrence returns -1. You need to store each valid index as you go and return the stored value after the loop ends.
Q: What would new Phrase("abcabc").findLastOccurrence("abc") return?
A: 3. The substring "abc" appears at index 0 and index 3. The last occurrence is at index 3.
This question connects directly to the String methods unit in AP CS A. The substring and indexOf methods tested here appear throughout the exam, in both free-response and multiple-choice sections. Mastering the index arithmetic in this problem makes every other String question easier.
The "use a helper method" pattern also connects to object-oriented design principles. In later units on inheritance and polymorphism, you will see similar patterns where one method delegates part of its work to another. Getting comfortable with that delegation here, where the logic is simpler, pays off later.
The while loop pattern in findLastOccurrence ("keep going until a sentinel value") is the same pattern used in reading input, searching arrays, and traversing linked structures. If you understand why the loop works here, you already understand sentinel-controlled loops generally.
AP CS A FRQ, 2017 AP Computer Science A, Phrase class, String manipulation Java, indexOf, substring, findNthOccurrence, replaceNthOccurrence, findLastOccurrence, string replacement Java, nth occurrence substring, AP CS A free response question 3, helper method pattern, sentinel loop, Java String methods, AP exam string questions, currentPhrase, precondition postcondition Java