Implementing
String Algorithms

Master Java's String methods, traverse characters with loops, and solve classic problems like searching, reversing, and substring extraction.

AP Computer Science A

What Is a String in Java?

A String is an immutable sequence of characters. Unlike primitive types, Strings are objects: each character lives at a specific index starting from \( 0 \) up to \( \text{length} - 1 \).

Essential String Methods

length()

Returns the number of characters. "Hi" → 2

charAt(i)

Returns the char at index i. Zero-based.

substring(a, b)

Returns chars from index a up to but not including index b.

indexOf(str)

Returns the first index of str, or -1 if not found.

equals(str)

Compares content. Never use == for String comparison.

compareTo(str)

Lexicographic compare. Returns 0 if equal, < 0 or > 0 otherwise.

Why String Algorithms Matter

String manipulation appears on nearly every AP exam. Understanding how to traverse, search, and build Strings is essential for both the multiple-choice and free-response sections.

1

Data processing: parsing user input, formatting output, and validating data.

2

Pattern matching: searching for keywords, counting occurrences, replacing substrings.

3

Transformation: reversing, encrypting, encoding, and compressing text.

Core Pattern: String Traversal

The fundamental pattern for processing every character in a String is a for loop from index \( 0 \) to \( \text{str.length()} - 1 \):

for (int i = 0; i < str.length(); i++) {
    char ch = str.charAt(i);
    // process ch
}

.equals() vs ==

This is the single most common source of bugs with Strings in Java. The two operations test fundamentally different things:

	.equals()	==
Tests	Content equality	Reference equality
Meaning	Same characters?	Same object in memory?
Use for Strings?	✓ Always	✕ Never
Example	"Hi".equals(s)	"Hi" == s

Understanding substring()

substring(a, b) returns characters from index a (inclusive) to index b (exclusive). Think of the indices as sitting between characters:

How to Solve String Problems

1

Identify the traversal: Do you need to visit every character, or only some? Decide your loop bounds.

2

Choose your tool: charAt() for single characters, substring() for sequences, indexOf() to search.

3

Build the result: Accumulate into a new String using concatenation: result += ch;

4

Handle edge cases: Empty strings, single characters, and off-by-one index errors.

5

Trace through: Manually walk through your code with a small test input to verify correctness.

Example 1: Counting a Character

Problem: Count how many times the letter 'a' appears in a given String.

public static int countChar(String str, char target) {
    int count = 0;
    for (int i = 0; i < str.length(); i++) {
        if (str.charAt(i) == target) {
            count++;
        }
    }
    return count;
}

Example 2: Reversing a String

Problem: Return the reverse of a given String. Since Strings are immutable, we build a new one character by character.

public static String reverse(String str) {
    String result = "";
    for (int i = str.length() - 1; i >= 0; i--) {
        result += str.charAt(i);
    }
    return result;
}

Example 3: Counting Substring Occurrences

Problem: Count how many times a substring appears within a larger String (non-overlapping).

public static int countSub(String str, String sub) {
    int count = 0;
    int idx = str.indexOf(sub);
    while (idx != -1) {
        count++;
        idx = str.indexOf(sub, idx + sub.length());
    }
    return count;
}

Example 4: Removing Characters

Problem: Remove all occurrences of a specific character from a String.

public static String removeChar(String str, char ch) {
    String result = "";
    for (int i = 0; i < str.length(); i++) {
        if (str.charAt(i) != ch) {
            result += str.charAt(i);
        }
    }
    return result;
}

Common Mistakes

✕ Using == for Strings

Comparing String content with == checks memory addresses, not characters. Always use .equals().

✕ Off-by-One in substring()

Forgetting the end index is exclusive. substring(0, 3) returns indices 0, 1, 2: not 3.

✕ IndexOutOfBounds

Accessing charAt(str.length()) crashes. Valid indices are 0 to \( \text{length()} - 1 \).

✕ Forgetting Immutability

Writing str.toUpperCase() without saving the result. Must do: str = str.toUpperCase();

✕ Null Pointer

Calling methods on a null String crashes. Check for null before calling .length() or .charAt().

String Methods Cheat Sheet

Method	Returns	Example
length()	int	"Cat".length() → 3
charAt(i)	char	"Cat".charAt(1) → 'a'
substring(a, b)	String	"Cat".substring(0, 2) → "Ca"
indexOf(s)	int	"Cat".indexOf("at") → 1
equals(s)	boolean	"Cat".equals("cat") → false
compareTo(s)	int	"A".compareTo("B") → < 0

Building Strings with Concatenation

Since Strings are immutable, each += creates a new String object. For the AP exam, this simple pattern is expected and acceptable:

String result = "";
for (int i = 0; i < str.length(); i++) {
    if (/* some condition */) {
        result += str.charAt(i);
    }
}
// result now contains filtered characters

Question 1 of 5

What is the value of "Hello".substring(1, 4)?

substring(1, 4) extracts characters at indices 1, 2, and 3 (the end index 4 is exclusive). Those characters are 'e', 'l', 'l' → "ell".

Question 2 of 5

Which correctly compares two String variables s1 and s2 for equal content?

.equals() compares the actual character content of two Strings. == compares memory references, compareTo() returns an int (not a boolean), and comparing only the first character is insufficient.

Question 3 of 5

Consider the following method:

public static String mystery(String s) {
  String result = "";
  for (int i = s.length() - 1; i >= 0; i--) {
    result += s.substring(i, i + 1);
  }
  return result;
}

▼ Tap to read passage

What does mystery("Code") return?

The loop iterates from index 3 down to 0. substring(i, i+1) extracts single characters: index 3 → "e", index 2 → "d", index 1 → "o", index 0 → "C". Concatenated: "edoC". This is a reverse algorithm.

Question 4 of 5

What is the value of "programming".indexOf("gram")?

indexOf() returns the index where the substring first begins. In "programming", the substring "gram" starts at index 3 (p-r-o-g-r-a-m-m-i-n-g).

Question 5 of 5

Consider the following code segment:

String s = "abcabc";
int count = 0;
for (int i = 0; i < s.length(); i++) {
  if (s.substring(i, i + 1).equals("b")) {
    count++;
  }
}

▼ Tap to read passage

What is the value of count after the code executes?

The loop checks each single-character substring against "b". In "abcabc", the character 'b' appears at indices 1 and 4. So count is incremented twice, giving count = 2. Note: substring(i, i+1) extracts a one-character String, and we correctly use .equals() to compare.

ImplementingString Algorithms

What Is a String in Java?

Essential String Methods

Why String Algorithms Matter

Core Pattern: String Traversal

.equals() vs ==

Understanding substring()

How to Solve String Problems

Example 1: Counting a Character

Example 2: Reversing a String

Example 3: Counting Substring Occurrences

Example 4: Removing Characters

Common Mistakes

String Methods Cheat Sheet

Building Strings with Concatenation

Question 1 of 5

Question 2 of 5

Question 3 of 5

Question 4 of 5

Question 5 of 5

Implementing
String Algorithms