2.10 Developing Algorithms Using Strings

String algorithms combine loops with String methods like charAt, substring, length, and indexOf to examine text one character or one substring at a time. The three standard goals are checking whether substrings have a property, counting substrings that meet criteria, and building a new string with the characters reversed. For AP Computer Science A, pay close attention to loop bounds and substring indices.

How Do String Algorithms Work in AP CSA?

String algorithms use loops to visit characters or substrings in a predictable order. Most AP CSA string tasks ask you to check a property, count matching substrings, or build a new string, so the key is choosing safe loop bounds and using charAt, substring, length, and .equals() correctly.

Why This Matters for the AP Computer Science A Exam

String processing shows up across both sections of the AP Computer Science A exam. On multiple choice, you trace loops that call String methods and determine output or pick the correct algorithm, so you need to read loop bounds and index math precisely. On free-response code writing, you may be asked to write a method that uses loops and conditionals along with String methods to analyze or transform text, which is exactly the pattern in this topic. Getting comfortable with character traversal and substring scanning makes these questions far more predictable.

Key Takeaways

• Traverse a string with a loop from index 0 to length() - 1, using charAt(i) to read each character.
• Build new strings with concatenation because String objects cannot be changed in place.
• Use substring(start, end) knowing that start is inclusive and end is exclusive.
• Standard string tasks include checking a property of substrings, counting substrings that match criteria, and reversing characters.
• Use .equals() to compare String content, not ==.
• Watch loop bounds and index math to avoid StringIndexOutOfBoundsException and off-by-one errors.

Core String Patterns

Character-by-Character Traversal

The most basic pattern reads each character using the string's length to control the loop and charAt() to access each position.

</>Java
String word = "hello";
for (int i = 0; i < word.length(); i++) {
    char ch = word.charAt(i);
    // Process this character
}

This pattern is the base for counting characters, finding specific letters, and checking string properties.

Building a New String

Many string algorithms build a result gradually. Since strings are immutable, you create a new string by concatenating pieces as you go.

</>Java
String original = "programming";
String result = "";
for (int i = 0; i < original.length(); i++) {
    char ch = original.charAt(i);
    if (ch != 'g') {       // example condition
        result += ch;
    }
}

Substring Scanning

Sometimes you compare pieces of a string instead of single characters. Slide a window across valid starting positions and compare each piece to a target.

The key is keeping your starting index in range so the substring call never runs past the end of the string.

Pattern Recognition

When you read a string problem, identify which goal it fits:

• Counting: how many times does something occur?
• Finding: where is the first or last occurrence?
• Filtering: which characters or substrings meet a condition?
• Transforming: how do we build a modified version?
• Comparing: how do parts of the string relate to each other?

Code Examples

Counting Characters

</>Java
public class CharacterCounting {
    // Count occurrences of a specific character
    public static int countChar(String text, char target) {
        int count = 0;
        for (int i = 0; i < text.length(); i++) {
            if (text.charAt(i) == target) {
                count++;
            }
        }
        return count;
    }

    // Count vowels in a string
    public static int countVowels(String text) {
        int count = 0;
        String vowels = "aeiouAEIOU";

        for (int i = 0; i < text.length(); i++) {
            char ch = text.charAt(i);
            if (vowels.indexOf(ch) >= 0) {  // Found in vowels string
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countChar("programming", 'g'));  // 2
        System.out.println(countVowels("programming"));     // 3
    }
}

Finding Patterns

</>Java
public class PatternFinding {
    // Find first occurrence of a character
    public static int findFirst(String text, char target) {
        for (int i = 0; i < text.length(); i++) {
            if (text.charAt(i) == target) {
                return i;  // Return index where found
            }
        }
        return -1;  // Not found
    }

    // Find last occurrence of a character  
    public static int findLast(String text, char target) {
        for (int i = text.length() - 1; i >= 0; i--) {
            if (text.charAt(i) == target) {
                return i;
            }
        }
        return -1;
    }

    // Check if string contains only digits
    public static boolean isAllDigits(String text) {
        if (text.length() == 0) return false;

        for (int i = 0; i < text.length(); i++) {
            char ch = text.charAt(i);
            if (ch < '0' || ch > '9') {  // Not a digit
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(findFirst("programming", 'r'));  // 1
        System.out.println(findLast("programming", 'r'));   // 4
        System.out.println(isAllDigits("12345"));           // true
        System.out.println(isAllDigits("123a5"));           // false
    }
}

String Transformation

</>Java
public class StringTransformation {
    // Remove all occurrences of a character
    public static String removeChar(String text, char toRemove) {
        String result = "";
        for (int i = 0; i < text.length(); i++) {
            char ch = text.charAt(i);
            if (ch != toRemove) {
                result += ch;
            }
        }
        return result;
    }

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

    // Replace all occurrences of one character with another
    public static String replaceChar(String text, char oldChar, char newChar) {
        String result = "";
        for (int i = 0; i < text.length(); i++) {
            char ch = text.charAt(i);
            if (ch == oldChar) {
                result += newChar;
            } else {
                result += ch;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(removeChar("programming", 'g'));      // "prorammin"
        System.out.println(reverse("hello"));                    // "olleh"
        System.out.println(replaceChar("hello", 'l', 'x'));     // "hexxo"
    }
}

The reverse method here is the standard "create a new string with the characters reversed" algorithm, done by walking the string from the last index back to 0.

Substring Analysis

</>Java
public class SubstringAnalysis {
    // Count occurrences of a substring
    public static int countSubstring(String text, String target) {
        int count = 0;
        int targetLen = target.length();

        // Check each possible starting position
        for (int i = 0; i <= text.length() - targetLen; i++) {
            String sub = text.substring(i, i + targetLen);
            if (sub.equals(target)) {
                count++;
            }
        }
        return count;
    }

    // Find all positions where substring occurs
    public static void findAllOccurrences(String text, String target) {
        int targetLen = target.length();

        for (int i = 0; i <= text.length() - targetLen; i++) {
            String sub = text.substring(i, i + targetLen);
            if (sub.equals(target)) {
                System.out.println("Found '" + target + "' at index " + i);
            }
        }
    }

    // Check if string is a palindrome
    public static boolean isPalindrome(String text) {
        int left = 0;
        int right = text.length() - 1;

        while (left < right) {
            if (text.charAt(left) != text.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(countSubstring("ababab", "ab"));  // 3
        findAllOccurrences("programming", "gr");             // Found 'gr' at index 3
        System.out.println(isPalindrome("racecar"));         // true
        System.out.println(isPalindrome("hello"));           // false
    }
}

countSubstring is the standard "count the substrings that meet criteria" pattern, and isPalindrome checks a property of the string by comparing characters from both ends.

Complex Pattern Processing

</>Java
public class ComplexPatterns {
    // Extract all digits from a string
    public static String extractDigits(String text) {
        String digits = "";
        for (int i = 0; i < text.length(); i++) {
            char ch = text.charAt(i);
            if (ch >= '0' && ch <= '9') {
                digits += ch;
            }
        }
        return digits;
    }

    // Count words in a string (simplified - splits on spaces)
    public static int countWords(String text) {
        if (text.length() == 0) return 0;

        int wordCount = 0;
        boolean inWord = false;

        for (int i = 0; i < text.length(); i++) {
            char ch = text.charAt(i);
            if (ch != ' ') {  // Non-space character
                if (!inWord) {
                    wordCount++;  // Starting a new word
                    inWord = true;
                }
            } else {  // Space character
                inWord = false;
            }
        }
        return wordCount;
    }

    // Remove consecutive duplicate characters
    public static String removeDuplicates(String text) {
        if (text.length() <= 1) return text;

        String result = "" + text.charAt(0);  // Start with first character

        for (int i = 1; i < text.length(); i++) {
            if (text.charAt(i) != text.charAt(i - 1)) {
                result += text.charAt(i);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(extractDigits("abc123def456"));    // "123456"
        System.out.println(countWords("hello world test"));   // 3
        System.out.println(removeDuplicates("aabbccdd"));     // "abcd"
    }
}

Common Errors and Debugging

StringIndexOutOfBoundsException

This happens when you try to access a character beyond the string's length.

Common cause: Off-by-one errors in loop bounds or substring operations.

Example scenario:

</>Java
String word = "hello";
for (int i = 0; i <= word.length(); i++) {  // Bug: should be <, not <=
    System.out.println(word.charAt(i));  // Crashes when i equals length
}

How to fix: Always use i < string.length() for character access.

Debugging tip: When working with substrings, double-check that your end index doesn't exceed the string length.

Incorrect Substring Bounds

Substring operations can be tricky because the end index is exclusive.

Common cause: Confusion about substring(start, end) parameters.

Example scenario:

</>Java
String text = "programming";
// Want to get "gram" (indices 3, 4, 5, 6)
String sub = text.substring(3, 7);  // Correct: end is exclusive, gives "gram"
String wrong = text.substring(3, 6); // Bug: would get "gra"

How to fix: Remember that substring(start, end) goes from start (inclusive) to end (exclusive), so the length of the result is end - start.

Forgetting String Immutability

Strings can't be modified, so operations like += create new string objects each time.

Common cause: Trying to modify a string directly or not understanding concatenation.

Example scenario:

</>Java
String word = "hello";
// word.charAt(0) = 'H';  // Does not work - charAt cannot be assigned

// Use concatenation instead:
word = "H" + word.substring(1);  // Creates new string "Hello"

How to fix: Build a new string with concatenation as you traverse.

How to Use This on the AP Computer Science A Exam

Code Tracing

On multiple choice, expect to trace loops that call String methods and report the output. Track the loop index, the current character from charAt(i), and any accumulator string after each pass. Watch for loops that run from the end of the string back to 0, since those usually signal a reversal.

Free Response

Free-response code writing often asks for a method that loops through a string and uses String methods to analyze or transform it. Read the specification closely: underline the return type, the parameters, and the exact behavior described in the examples. Then pick the matching pattern, whether that is counting, checking a property, or building a reversed string.

Common Trap

Substring bounds and loop bounds cause most string mistakes. When scanning for a substring of length targetLen, your loop should run while i <= text.length() - targetLen so the final substring(i, i + targetLen) stays in range.

Practice Problems

Problem 1: Pig Latin Converter

Write a method that converts a single word to Pig Latin. If the word starts with a vowel, add "way" to the end. If it starts with a consonant, move the first letter to the end and add "ay".

</>Java
public static String toPigLatin(String word) {
    // Your solution here
}

Solution:

</>Java
public static String toPigLatin(String word) {
    if (word.length() == 0) return word;

    String vowels = "aeiouAEIOU";
    char firstChar = word.charAt(0);

    if (vowels.indexOf(firstChar) >= 0) {
        // Starts with vowel
        return word + "way";
    } else {
        // Starts with consonant
        return word.substring(1) + firstChar + "ay";
    }
}

Test cases: "apple" -> "appleway", "hello" -> "ellohay"

Problem 2: Caesar Cipher

Write a method that shifts each letter in a string by a fixed number of positions in the alphabet:

</>Java
public static String caesarCipher(String text, int shift) {
    // Shift each letter by the specified amount
    // Your solution here
}

Solution:

</>Java
public static String caesarCipher(String text, int shift) {
    String result = "";

    for (int i = 0; i < text.length(); i++) {
        char ch = text.charAt(i);

        if (ch >= 'a' && ch <= 'z') {
            // Lowercase letter
            int shifted = ((ch - 'a' + shift) % 26 + 26) % 26;
            result += (char)('a' + shifted);
        } else if (ch >= 'A' && ch <= 'Z') {
            // Uppercase letter  
            int shifted = ((ch - 'A' + shift) % 26 + 26) % 26;
            result += (char)('A' + shifted);
        } else {
            // Not a letter, keep as-is
            result += ch;
        }
    }
    return result;
}

This uses modular arithmetic to wrap around the alphabet so a shift past z returns to a.

Problem 3: Count Matching Substrings

Write a method that counts how many times a target substring appears in a longer string, including overlapping occurrences.

</>Java
public static int countMatches(String text, String target) {
    // Count overlapping occurrences of target in text
    // Your solution here
}

Solution:

</>Java
public static int countMatches(String text, String target) {
    int count = 0;
    int targetLen = target.length();

    if (targetLen == 0) return 0;

    for (int i = 0; i <= text.length() - targetLen; i++) {
        if (text.substring(i, i + targetLen).equals(target)) {
            count++;
        }
    }
    return count;
}

Example: countMatches("ababab", "ab") returns 3, and countMatches("aaaa", "aa") returns 3 because overlaps are counted.

Common Misconceptions

• Using == to compare String content. Use .equals(); == checks whether two variables point to the same object, not whether the characters match.
• Thinking charAt() lets you change a character. It only reads a character. To change text, build a new string with concatenation or substring.
• Assuming the end index of substring(start, end) is included. It is exclusive, so the result length is end - start.
• Looping with i <= text.length() for character access. That goes one index too far and throws StringIndexOutOfBoundsException; use i < text.length().
• For substring scanning, stopping the loop at text.length(). Stop at text.length() - targetLen so the substring call stays in range.
• Believing concatenation changes the original string. Each += creates a new string; the original is unchanged because strings are immutable.

Related AP Computer Science A Guides

• 2.1 Algorithms with Selection and Repetition
• 2.7 While Loops
• 2.8 For Loops
• 2.9 Implementing Selection and Iteration Algorithms
• 2.6 Equivalent Boolean Expressions
• 2.11 Nested Iteration
• 2.12 Informal Code Analysis