StringCoder: 2008 FRQ 2

Encoding and decoding words against a shared "master string" is the puzzle behind this AP Computer Science A free-response question — one method reassembles a word from a list of substring references, and the other breaks a word back down into those references using a helper method you don't have to write yourself.

What This FRQ Tests

• AP CSA units: primarily Unit 4 (Iteration), with heavy String and ArrayList work mixed in
• Core skill: looping to accumulate a String result, and looping with a condition based on "how much work is left" rather than a fixed count
• Secondary skill: trusting a given helper method to do part of the work, without needing to know how it's implemented internally
• Official category: officially FRQ 2 by this exam's own printed numbering — but 2008 predates the fixed FRQ-number-to-category order introduced with the 2019–2020 CED redesign, where slot 2 is reserved for "Classes." This question doesn't cleanly fit any single modern category: it's a blend of String-processing logic and ArrayList traversal/construction, built entirely around methods you write for an already-existing class rather than designing a new one.

The Setup

• A single shared masterString contains every letter of the alphabet, some possibly more than once.
• A StringPart class (not modified) represents one substring of the master string by its position:
  • StringPart(int start, int length)
  • int getStart()
  • int getLength()
• A StringCoder class holds:
  • private String masterString
  • private StringPart findPart(String str) — a given helper (implementation not shown) that returns a StringPart matching the beginning of str, with length at least 1
• You're asked to write two methods:
  • decodeString(ArrayList<StringPart> parts) — rebuilds the original String from a list of parts
  • encodeString(String word) — breaks word down into a list of matching parts, using findPart

Part (a): Writing decodeString(ArrayList<StringPart> parts)

The Rule, Broken Down

1. Each StringPart names a substring of masterString: it starts at getStart() and runs for getLength() characters.
2. Decoding means pulling out each of those substrings, in the order they appear in parts, and concatenating them together.

Step-by-Step Approach

1. Start with an empty String to build the result.
2. Loop over every index of parts.
3. For each StringPart, pull its matching substring out of masterString.
4. Append that substring onto the result.
5. After the loop, return the finished result.

The Code

public String decodeString(ArrayList<StringPart> parts)
{
    String result = "";

    for (int i = 0; i < parts.size(); i++)
    {
        StringPart part = parts.get(i);
        result = result + masterString.substring(part.getStart(), part.getStart() + part.getLength());
    }

    return result;
}

Why Each Piece Matters

• part.getStart() + part.getLength() as the second substring argument — substring(from, to) stops before index to, so adding the start and the length together lands exactly one past the substring's last character, which is exactly what substring's second argument expects.
• Building result with repeated concatenation inside the loop — since parts is already stored in the correct order, appending each decoded piece in loop order naturally reconstructs the original sequence.
• Never modifying masterString or parts — this method only reads from both; nothing about decoding requires changing either one.

Tracing the Example

The question itself defines the word "overeager" as the encoding [(37, 3), (14, 2), (46, 2), (9, 2)] against the master string "sixtyzipperswerequicklypickedfromthewovenjutebag". Extracting each substring:

Concatenating in order: "ove" + "re" + "ag" + "er" = "overeager" — exactly the word the question uses to illustrate what this list of parts represents.

Common Mistakes to Avoid

• Using part.getStart() + part.getLength() - 1 as the second argument. Since substring's to index is already exclusive, subtracting 1 would chop off the substring's last character.
• Assuming there are always exactly four parts. The loop has to run over parts.size(), whatever that happens to be — not a hardcoded count based on one example.
• Concatenating out of order (for example, iterating backwards through parts). The order given in parts is the order the decoded pieces must appear in.

Part (b): Writing encodeString(String word)

The Rule, Broken Down

1. Repeatedly find a StringPart that matches the beginning of whatever part of word hasn't been matched yet, using the given findPart helper.
2. Add that part to the result list.
3. Remove however many characters that part covered from the front of the remaining word.
4. Repeat until nothing is left, then return the collected list.

Step-by-Step Approach

1. Create an empty ArrayList<StringPart> to hold the result.
2. Keep track of the "remaining" text still left to encode, starting as the full word.
3. While there's still text remaining, call findPart on it to get a part matching its beginning.
4. Add that part to the result list.
5. Shrink remaining by cutting off however many characters that part covered.
6. Once remaining is empty, return the result list.

The Code

public ArrayList<StringPart> encodeString(String word)
{
    ArrayList<StringPart> parts = new ArrayList<StringPart>();
    String remaining = word;

    while (remaining.length() > 0)
    {
        StringPart part = findPart(remaining);
        parts.add(part);
        remaining = remaining.substring(part.getLength());
    }

    return parts;
}

Why Each Piece Matters

• A while loop, not a for loop — the number of parts needed to encode a word isn't known ahead of time; it depends entirely on how much of the word each call to findPart manages to match.
• remaining.substring(part.getLength()) — the one-argument form of substring returns everything from that index to the end of the string, which is exactly "drop the characters that were just matched off the front."
• Calling findPart directly — it's a private method, but private only blocks access from outside the class; encodeString is a method of the same StringCoder class, so it's allowed to call it freely.
• Trusting findPart as a black box — its own matching strategy ("implementation not shown") doesn't need to be known or reproduced here; the method's documented behavior (a match of length at least 1, at the start of the given string) is all encodeString needs to rely on.

Tracing the Example

findPart's exact matching logic isn't given to us, so encodeString's precise output can't be independently predicted from scratch — but the question already tells us what findPart returns at each step for this specific word, since it defines "overeager" as encoding to exactly [(37, 3), (14, 2), (46, 2), (9, 2)]. Tracing the loop assuming those are the values findPart returns, in that order:

The loop stops once remaining is empty, having collected exactly [(37, 3), (14, 2), (46, 2), (9, 2)] — matching the question's own example precisely. This confirms the loop's structure is correct; the specific StringPart returned on each call is entirely findPart's responsibility, not something encodeString computes itself.

Common Mistakes to Avoid

• Forgetting to update remaining inside the loop, which would call findPart on the same unchanged string forever and never terminate.
• Using remaining.substring(0, part.getLength()) instead of remaining.substring(part.getLength()) — the first keeps the matched prefix instead of removing it, which is backwards.
• Trying to reimplement findPart's matching logic by hand inside encodeString. The problem explicitly requires calling the helper method, not duplicating its behavior.
• Recomputing the matched length instead of using part.getLength() — the StringPart returned by findPart already carries this information; there's no need to figure it out separately.

Key Takeaways

• Rebuilding something from a list of known pieces (decoding) is a simple index-based for loop over that list.
• Building something up when you don't know in advance how many steps it'll take (encoding, one greedy match at a time) calls for a while loop driven by "is there still work left," not a for loop with a fixed count.
• A private helper method is only hidden from other classes — calling it from another method inside the same class, and trusting its documented behavior without knowing its internals, is exactly what it's there for.