2.10 Developing Algorithms Using Strings

String algorithms combine loops with String methods to process text data systematically. These algorithms let you analyze, transform, and search through strings by examining characters individually or working with substrings. Understanding these patterns is essential for solving text processing problems that appear frequently in programming.

The foundation of string algorithms is treating strings as sequences of characters that can be traversed with loops. By combining iteration with String methods like charAt(), substring(), and length(), you can implement powerful text processing solutions. These algorithms form the basis for everything from input validation to pattern searching.

• Major concepts: Character-by-character processing, substring analysis, pattern counting, string building with loops
• Why this matters for AP: Essential for FRQ string manipulation problems, appears in algorithm implementation questions
• Common pitfalls: Index out of bounds errors, off-by-one mistakes with substring, forgetting string immutability
• Key vocabulary: Character processing, substring extraction, string traversal, pattern matching, accumulator pattern
• Prereqs: String methods (.charAt(), .substring(), .length()), for/while loops, boolean logic

Key Concepts

Character-by-Character Processing

The most fundamental string algorithm pattern is examining each character in a string individually. You use the string's length to control your loop and charAt() to access each character.

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

This pattern forms the foundation for counting characters, finding specific letters, or analyzing string properties.

The Accumulator Pattern for Strings

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

String original = "programming";
String result = "";
for (int i = 0; i < original.length(); i++) {
    // Add to result based on some condition
    if (condition) {
        result += original.charAt(i);
    }
}

Substring Processing

Sometimes you need to examine pieces of a string rather than individual characters. This involves nested loops or careful index management to extract and analyze substrings.

The key is understanding how substring indices work and avoiding index out of bounds errors.

Pattern Recognition Strategies

When solving string problems, look for these common patterns:

• Counting: How many times does something occur?
• Finding: Where is the first/last occurrence?
• Filtering: Which characters/substrings meet criteria?
• Transforming: How do we modify the string?
• Comparing: How do parts of the string relate?

Code Examples

Counting Characters

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

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

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"
    }
}

Substring Analysis

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
    }
}

Complex Pattern Processing

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:

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:

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

How to fix: Remember that substring(start, end) goes from start (inclusive) to end (exclusive).

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:

String word = "hello";
word.charAt(0) = 'H';  // Compile error - can't modify

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

How to fix: Use string concatenation or StringBuilder for building strings in loops.

Practice Problems

Problem 1: Pig Latin Converter

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

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

Solution:

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:

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

Solution:

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

Key insight: Use modular arithmetic to wrap around the alphabet.

Problem 3: Longest Common Prefix

Write a method that finds the longest common prefix among an array of strings:

public static String longestCommonPrefix(String[] strings) {
    // Find the longest prefix shared by all strings
    // Your solution here
}

Solution:

public static String longestCommonPrefix(String[] strings) {
    if (strings.length == 0) return "";

    String prefix = "";
    int minLength = strings[0].length();

    // Find shortest string length
    for (int i = 1; i < strings.length; i++) {
        if (strings[i].length() < minLength) {
            minLength = strings[i].length();
        }
    }

    // Check each character position
    for (int pos = 0; pos < minLength; pos++) {
        char ch = strings[0].charAt(pos);

        // Check if all strings have same character at this position
        for (int i = 1; i < strings.length; i++) {
            if (strings[i].charAt(pos) != ch) {
                return prefix;  // Found mismatch
            }
        }
        prefix += ch;  // All strings match at this position
    }
    return prefix;
}

Example: {"flower", "flow", "flight"} → "fl"

AP Exam Connections

String processing with loops is a favorite topic for AP Computer Science A FRQ questions.

Multiple Choice Patterns

You'll see questions about tracing through string processing loops, determining output, or identifying correct algorithm implementations. Pay attention to loop bounds and string method calls.

FRQ Applications

FRQ 1 (Methods and Control Structures): Often requires implementing string processing methods that use loops to analyze or transform text.

FRQ 2 (Class Design): Classes might have string attributes that need processing methods, requiring loop-based string algorithms.

FRQ 3 (Array/ArrayList): You might need to process arrays of strings or use string methods while processing other data structures.

FRQ 4 (2D Array): Sometimes involves processing strings stored in 2D arrays or generating string representations of 2D data.

Quick Test-Taking Tips

When working with string problems, always check your loop bounds carefully. Remember that charAt() uses 0-based indexing and substring() end parameter is exclusive.

For string building problems, trace through your accumulator variable to ensure you're building the result correctly. Test your logic with simple examples before applying to complex cases.

If you see string comparison in loops, make sure you're using .equals() for content comparison, not == for reference comparison.