Computer Science A

Course Progress 0/0
Sprint View
Week 19 2017 FRQ 3

2017 FRQ 3

9 min read

FRQ Question 3

This question involves the Phrase class, which contains methods for working with phrases and finding/replacing occurrences of strings within them.

You will write two methods for the Phrase class:

  • Part (a): replaceNthOccurrence
  • Part (b): findLastOccurrence

Both methods will use the provided findNthOccurrence method.

Analyze the Problem: Walkthrough

String Searching and Manipulation

Problem Type: String processing / loops / method calls

Difficulty: Medium

You are given a Phrase object that contains:

  • currentPhrase (String) - the phrase being worked with
  • findNthOccurrence(String str, int n) - finds the nth occurrence of a substring

You must implement:

  1. Replace the nth occurrence of a substring with another string (replaceNthOccurrence)
  2. Find the last occurrence of a substring (findLastOccurrence)

Mental Model

Think of the phrase as a text document you’re searching through:

  • findNthOccurrence(str, n) is like a search function that jumps to the nth match
  • replaceNthOccurrence(str, n, repl) finds and replaces the nth occurrence
  • findLastOccurrence(str) keeps searching forward until no more matches exist

Checkpoint: Before coding, make sure you can answer:

  • What does findNthOccurrence return when the nth occurrence doesn’t exist?
  • How do you split a string at a specific index and reconstruct it with a replacement?
  • How do you keep searching for occurrences until you’ve found the last one?

FRQ Question Part A

Part (a): replaceNthOccurrence Method

Write the Phrase method replaceNthOccurrence, which will replace the nth occurrence of the string str with the string repl. If the nth occurrence does not exist, currentPhrase remains unchanged.

Requirements:

  • You must use findNthOccurrence appropriately to receive full credit
  • If the nth occurrence does not exist, currentPhrase remains unchanged
  • The method modifies currentPhrase (it’s a void method)

Examples:

Phrase phrase = new Phrase("A cat ate late.");
phrase.replaceNthOccurrence("at", 1, "ot");  
// currentPhrase becomes "A cot ate late."

phrase = new Phrase("A cat ate late.");
phrase.replaceNthOccurrence("at", 6, "xx");  
// currentPhrase unchanged (6th occurrence doesn't exist)

Walkthrough (How to Think About It)

Step 1: Find the nth occurrence

  • Call findNthOccurrence(str, n) to get the index
  • Store the result in a variable

Step 2: Check if replacement should occur

  • If findNthOccurrence returns -1, the occurrence doesn’t exist
  • Only proceed with replacement if a valid index is returned

Step 3: Construct the new phrase

  • Get everything before the occurrence: currentPhrase.substring(0, index)
  • Add the replacement string: repl
  • Get everything after the occurrence: currentPhrase.substring(index + str.length())
  • Combine all three parts and assign back to currentPhrase

Common pitfall: Don’t forget that after finding the occurrence at index, the original substring has length str.length(), not repl.length().

FRQ Question Part B

Part (b): findLastOccurrence Method

Write the Phrase method findLastOccurrence. This method finds and returns the index of the last occurrence of a given string in currentPhrase. If the given string is not found, -1 is returned.

Requirements:

  • You must use findNthOccurrence appropriately to receive full credit
  • Returns the index of the last occurrence of the string
  • Returns -1 if the string is not found
  • The currentPhrase must not be modified

Examples:

Phrase phrase = new Phrase("A cat ate late.");
phrase.findLastOccurrence("at");  // returns 11 (in "late")

phrase = new Phrase("A cat ate late.");
phrase.findLastOccurrence("bat");  // returns -1 (not found)

Walkthrough (How to Think About It)

Step 1: Set up a loop to find successive occurrences

  • Start with occurrence = 1
  • Call findNthOccurrence(str, 1), then findNthOccurrence(str, 2), etc.

Step 2: Keep track of the last valid occurrence found

  • Store each valid index as you find it
  • When you get -1, you know the previous index was the last one

Step 3: Handle the case where no occurrences exist

  • If the first call to findNthOccurrence(str, 1) returns -1, return -1 immediately

Algorithm Approaches:

Approach 1: Keep searching until you hit -1

Code Runner Challenge

AP CSA 2017 FRQ - Phrase

View IPYNB Source 
occurrence = 1
lastFound = -1
while true:
    index = findNthOccurrence(str, occurrence)
    if index == -1:
        return lastFound
    lastFound = index
    occurrence++
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Approach 2: Look ahead

occurrence = 1
index = findNthOccurrence(str, occurrence)
while index != -1:
    occurrence++
    nextIndex = findNthOccurrence(str, occurrence)
    if nextIndex == -1:
        return index
    index = nextIndex
return -1

Key insight: You need to keep calling findNthOccurrence with increasing values of n until it returns -1, meaning no more occurrences exist.

FRQ Question Part A

Part (a):replaceNthOccurrence Method

Write the Phrase method replaceNthOccurrence, which will replace the nth occurrence of the string str with the string repl. If the nth occurrence does not exist, currentPhrase remains unchanged.

Requirements:

  • You must use findNthOccurrence appropriately to receive full credit.
  • If the nth occurrence does not exist, currentPhrase remains unchanged.

FRQ Question Part B

Part (b): findLastOccurrence Method

Write the Phrase method findLastOccurrence. This method finds and returns the index of the last occurrence of a given string in currentPhrase. If the given string is not found, -1 is returned.

Requirements:

  • You must use findNthOccurrence appropriately to receive full credit.
  • Returns the index of the last occurrence of the string.
  • Returns -1 if the string is not found.
  • The currentPhrase must not be modified.

// CODE_RUNNER: AP CSA 2017 FRQ - Phrase

public class Phrase {

private String currentPhrase;

/** Constructor */
public Phrase(String p) {
    currentPhrase = p;
}

/** Returns the index of the nth occurrence of str */
public int findNthOccurrence(String str, int n) {
    int count = 0;
    int index = 0;

    while (index <= currentPhrase.length() - str.length()) {
        int found = currentPhrase.indexOf(str, index);
        if (found == -1) {
            return -1;
        }
        count++;
        if (count == n) {
            return found;
        }
        index = found + 1;  // Move to next position (not found + str.length())
    }
    return -1;
}

/** PART (a): replaceNthOccurrence */
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());
    }
}

/** PART (b): findLastOccurrence */
public int findLastOccurrence(String str) {
    int occurrence = 1;
    int lastIndex = -1;
    
    while (true) {
        int index = findNthOccurrence(str, occurrence);
        if (index == -1) {
            return lastIndex;
        }
        lastIndex = index;
        occurrence++;
    }
}

/** Getter for testing */
public String toString() {
    return currentPhrase;
}

/* There may be instance variables, constructors, and methods that are not shown. */ }

// CODE_RUNNER: AP CSA 2017 FRQ - Phrase

public class Main {

    private String currentPhrase;

    /** Constructor */
    public Main(String p) {
        currentPhrase = p;
    }

    /** Returns the index of the nth occurrence of str */
    public int findNthOccurrence(String str, int n) {
        int count = 0;
        int index = 0;

        while (index <= currentPhrase.length() - str.length()) {
            int found = currentPhrase.indexOf(str, index);
            if (found == -1) {
                return -1;
            }
            count++;
            if (count == n) {
                return found;
            }
            index = found + str.length();
        }
        return -1;
    }

    /** PART (a): replaceNthOccurrence */
    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());
        }
    }

    /** PART (b): findLastOccurrence */
    public int findLastOccurrence(String str) {
        int n = 1;
        int last = -1;

        while (findNthOccurrence(str, n) != -1) {
            last = findNthOccurrence(str, n);
            n++;
        }

        return last;
    }

    public void driver() {
        System.out.println("Original phrase: " + currentPhrase);

        replaceNthOccurrence("hello", 2, "hi");
        System.out.println("After replaceNthOccurrence: " + currentPhrase);

        int lastIndex = findLastOccurrence("world");
        System.out.println("Last occurrence of 'world': " + lastIndex);
    }

    /** Main entry point */
    public static void main(String[] args) {
        Main tester = new Main("hello world hello world");
        tester.driver();
    }
}

Main.main(null);

Scoring Guidelines

Part (a): replaceNthOccurrence - 4 points

Calling findNthOccurrence - 1 point

  • Calls findNthOccurrence(str, n) with appropriate parameters

Determining if replacement should occur - 1 point

  • Uses the result from findNthOccurrence to determine whether the nth occurrence exists
  • Typically checks if the returned index is not -1

Constructing the new phrase - 2 points

  • 1 point: Uses substring to get the part of currentPhrase before the nth occurrence
  • 1 point: Uses substring to get the part of currentPhrase after the nth occurrence
  • Combines these parts with repl in the correct order
  • Assigns the result back to currentPhrase

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());
    }
}

Part (b): findLastOccurrence - 5 points

Calling findNthOccurrence in a loop - 2 points

  • 1 point: Calls findNthOccurrence with appropriate parameters
  • 1 point: Calls findNthOccurrence multiple times in a loop to find successive occurrences

Loop continuation condition - 1 point

  • Loop continues while occurrences of str are still being found
  • Typically checks if findNthOccurrence returns -1

Tracking the last occurrence found - 1 point

  • Stores/tracks the index of occurrences as they are found
  • Maintains the most recent valid index

Returning the correct value - 1 point

  • Returns the index of the last occurrence when no more occurrences exist
  • Returns -1 if no occurrences are found

Sample Solution:

public int findLastOccurrence(String str) {
    int occurrence = 1;
    int lastIndex = -1;
    
    while (true) {
        int index = findNthOccurrence(str, occurrence);
        if (index == -1) {
            return lastIndex;
        }
        lastIndex = index;
        occurrence++;
    }
}

Alternative Solution for Part (b)

public int findLastOccurrence(String str) {
    int occurrence = 1;
    int index = findNthOccurrence(str, occurrence);
    
    while (index != -1) {
        occurrence++;
        int nextIndex = findNthOccurrence(str, occurrence);
        if (nextIndex == -1) {
            return index;
        }
        index = nextIndex;
    }
    
    return -1;
}

Why these approaches work

Part (a):

  • findNthOccurrence does the hard work of finding where to replace
  • We just need to rebuild the string: [before] + [replacement] + [after]
  • The check for -1 ensures we don’t modify the phrase when the occurrence doesn’t exist

Part (b):

  • By incrementally calling findNthOccurrence(str, 1), then findNthOccurrence(str, 2), etc., we walk through all occurrences
  • When we get -1, we know the previous occurrence was the last one
  • The loop naturally handles the case where no occurrences exist (returns -1 on first call)

Quick Edge Tests

// Edge case: overlapping occurrences
Phrase p = new Phrase("aaaa");
System.out.println(p.findLastOccurrence("aa"));  // 2
p.replaceNthOccurrence("aa", 1, "b");
System.out.println(p);  // "baa"

// Edge case: single character
Phrase p2 = new Phrase("hello");
System.out.println(p2.findLastOccurrence("l"));  // 3
p2.replaceNthOccurrence("l", 2, "L");
System.out.println(p2);  // "heLlo"

// Edge case: not found
Phrase p3 = new Phrase("hello");
System.out.println(p3.findLastOccurrence("z"));  // -1
p3.replaceNthOccurrence("z", 1, "x");
System.out.println(p3);  // "hello" (unchanged)

Key Points to Remember

  1. Use findNthOccurrence: Both parts require you to call this method - don’t reimplement the search logic
  2. Handle -1 properly: Check for -1 before attempting any string manipulation
  3. Index arithmetic: When removing a substring, remember to skip str.length() characters, not repl.length()
  4. Loop strategy: For Part (b), keep incrementing the occurrence counter until you get -1
  5. Overlapping occurrences: findNthOccurrence should increment by 1, not by str.length(), to catch overlapping matches

Course Timeline