Implementing String Algorithms | AP CSA Unit 2 Study Guide

Getting Started

In programming, text is one of the most common forms of data we work with. A String in Java is an object that represents a sequence of characters. To perform meaningful tasks—like searching for a name, validating a password, or extracting data from a sentence—we need reliable ways to process these strings. This section covers the fundamental algorithms for traversing and manipulating String objects to build more complex programs.

What You Should Be Able to Do

Create String objects using both literals and the String constructor.
Explain the concept of immutability and how it applies to String objects.
Use the length(), substring(), and indexOf() methods to analyze and create new strings.
Implement a loop to traverse a String to examine its contents.
Trace the execution of code that uses standard String methods and loops.

Key Concepts & Java Implementation

The Core Idea

A String algorithm is a formal process or set of rules for manipulating a sequence of characters. Most String algorithms involve traversing, or moving through, the string to inspect its characters or find patterns. For example, you might traverse a string to count the number of vowels or to find the position of a specific word.

A critical concept in Java is that String objects are immutable. This means that once a String object is created, its internal sequence of characters can never be changed. Any method that appears to "modify" a string, such as substring(), does not alter the original String. Instead, it creates and returns a brand new String object containing the result. This is a key design feature that ensures predictability and security when working with text data.

Syntax & Implementation

There are two primary ways to create a String object in Java.

String Literal: A sequence of characters enclosed in double quotes. This is the most common and efficient way to create a string.
Constructor: The String class provides a constructor, which is a special method used to initialize a newly created object. You can create a String by passing another string to its constructor using the new keyword.


// 1. Using a String literal

String greeting = "Hello, World!";


// 2. Using the String constructor

String farewell = new String("Goodbye!");

The most common String algorithms are built using a combination of loops and the following core methods.

Method Signature	Purpose	Java Example
`int length()`	Returns the number of characters in the string.	`int len = "Java".length(); // len is 4`
`int indexOf(String str)`	Returns the starting index of the first occurrence of `str`. Returns -1 if `str` is not found.	`int pos = "apple".indexOf("p"); // pos is 1`
`String substring(int from, int to)`	Returns a new string containing characters from index `from` up to, but not including, index `to`.	`String s = "computer".substring(0, 4); // s is "comp"`
`String substring(int from)`	Returns a new string containing characters from index `from` to the end of the string.	`String s = "computer".substring(4); // s is "uter"`

Annotated Java Example: String Traversal

A common algorithm is to traverse a string to find or count occurrences of a smaller string. The following example counts how many times the letter "a" appears in a word.


public class StringAlgorithms {

    public static int countOccurrences(String text, String target) {

        int count = 0;

        int currentIndex = 0;


        // Loop as long as we keep finding the target string

        while (currentIndex < text.length()) {

            // Find the next occurrence of the target starting from currentIndex

            int foundIndex = text.indexOf(target, currentIndex);


            if (foundIndex == -1) {

                // If not found, we are done. Exit the loop.

                break;

            } else {

                // If found, increment the count

                count++;

                // Move the starting point for the next search past the found instance

                currentIndex = foundIndex + 1;

            }

        }

        return count;

    }


    public static void main(String[] args) {

        String sentence = "Java is a popular programming language.";

        int a_count = countOccurrences(sentence, "a");

        System.out.println("The letter 'a' appears " + a_count + " times."); // Prints 6

    }

}

Tracing & Analysis

Let's trace the countOccurrences("banana", "a") call to understand the traversal algorithm.

`currentIndex`	`text.indexOf("a", currentIndex)`	`foundIndex`	`count`	Notes
0	`text.indexOf("a", 0)`	1	1	"a" found at index 1. `currentIndex` becomes 2.
2	`text.indexOf("a", 2)`	3	2	"a" found at index 3. `currentIndex` becomes 4.
4	`text.indexOf("a", 4)`	5	3	"a" found at index 5. `currentIndex` becomes 6.
6	`text.indexOf("a", 6)`	-1	3	No more "a"s found. The `break` executes.

Analysis: This algorithm correctly traverses the string by updating its search position (currentIndex) after each successful find. By starting the next indexOf search at foundIndex + 1, it ensures the loop makes progress and doesn't find the same instance of the target repeatedly. This pattern of "loop, find, and update position" is a cornerstone of many String processing tasks.

Java Syntax Quick-Reference

String s = "text";: Creates a new String object using a literal.
String s = new String("text");: Creates a new String object using its constructor.
s.length(): Returns the integer length of the Strings.
s.indexOf(str): Returns the starting index of the first occurrence of str in s, or -1 if not found.
s.substring(from): Returns a new String that is a copy of the characters from index from to the end of s.
s.substring(from, to): Returns a new String that is a copy of the characters from index from up to (but not including) index to.

Core Code Examples & Terminology

String Literal: A sequence of characters in source code that is enclosed in double quotes (e.g., "Hello"). It directly represents a String object.
Constructor: A special method that is called to create and initialize an object when using the new keyword.
Immutable: An object whose state cannot be modified after it is created. In Java, String objects are immutable.
Index: An integer value that specifies the position of a character within a String. Java String indices are 0-based, meaning the first character is at index 0.
Core Snippet 1 (String Creation):
```
String literalStr = "AP CSA";

String constructedStr = new String("AP CSA");
```
This shows the two ways to instantiate a String object with the same sequence of characters.

Core Snippet 2 (Extracting a Substring):


String data = "NAME:John Doe";

int colonIndex = data.indexOf(":");

String name = data.substring(colonIndex + 1); // name is "John Doe"

This code finds a delimiter (:) and extracts the substring that follows it.

Core Snippet 3 (Character-by-Character Traversal):


String word = "loop";

for (int i = 0; i < word.length(); i++) {

    String letter = word.substring(i, i + 1);

    System.out.println(letter);

}

This for loop iterates through a string, printing each character on a new line.

Core Skill Check

Code Tracing: What is the final value of result after this Java code runs: String s = "absolute"; String result = s.substring(1, s.indexOf("u"));?
- Answer: "bsol"
Debugging: Identify the runtime error in this Java code: String word = "test"; String last = word.substring(word.length());.
- Answer: StringIndexOutOfBoundsException. The valid index range for substring is from 0 to word.length(). Calling substring(4) on a string of length 4 is valid (it returns an empty string), but any index greater than 4 would be an error. The prompt has a subtle error; substring(word.length()) is actually valid. A better example would be word.substring(word.length() + 1) or trying to access a character at word.length(). Let's correct this.
- Corrected Debugging Prompt: Identify the runtime error in this Java code: String word = "test"; String c = word.substring(4, 5);.
- Answer: StringIndexOutOfBoundsException. The to index (5) is greater than the string's length (4).
Application: Write a single line of Java code that gets the first three characters of a String named str.
- Answer: String firstThree = str.substring(0, 3);

Common Misconceptions & Errors

Thinking String Methods Modify the Original String: A common mistake is to call a method like s.substring(1); and assume s has changed. Strings are immutable. You must capture the returned value: String newS = s.substring(1);.
substring(from, to) Index Confusion: Remember the second parameter (to) is exclusive. The substring runs from the from index up to, but not including, the to index. "abcde".substring(1, 3) is "bc", not "bcd".
Off-by-One Errors in Loops: When looping from i = 0 to s.length() - 1, the last valid index is s.length() - 1. Using s.length() as an index in substring can cause an StringIndexOutOfBoundsException if it's not the start index.
Ignoring indexOf's -1 Return Value: If indexOf does not find the substring, it returns -1. Passing -1 to substring will cause a runtime error. Always check for -1 before using the result as an index.

Summary

Implementing String algorithms is a fundamental skill in Java programming. It involves using loops to traverse strings and core methods like length(), indexOf(), and substring() to analyze and manipulate them. The most important concept to remember is that String objects are immutable; methods that process strings always return new String objects rather than modifying the original. By combining these methods within loops, you can build powerful algorithms to search, extract, and validate any text-based data. Mastering this pattern is essential for solving a wide range of programming problems.

Implementing String Algorithms - AP Computer Science A Study Guide