Strings - AP Computer Science Principles

SECTION 1

Historical Context & Motivation

Before computers could process text, they operated almost exclusively on numerical data—calculations for ballistics, census tabulation, and cryptanalysis. The ability to represent, store, and manipulate strings—ordered sequences of characters—was a critical breakthrough that transformed computing from a purely mathematical tool into a platform for human communication, information retrieval, and software development. The evolution of string representation mirrors the broader story of how computing became accessible to people beyond mathematicians and engineers, enabling everything from word processors and search engines to modern social media platforms.

1963 • ASCII Standard Published

The American Standard Code for Information Interchange assigned numeric codes (0–127) to English letters, digits, and control characters, establishing a universal way to encode text as binary data inside computers.

1972 • C Language & Null-Terminated Strings

The C programming language introduced the convention of representing strings as arrays of characters terminated by a null byte (\0), a design that deeply influenced how hardware and software handled text for decades.

1991 • Unicode 1.0 Released

Unicode expanded character encoding to support scripts from virtually every written language, eventually encompassing over 149,000 characters and making global text processing feasible within a single standard.

1995 • Java & Immutable String Objects

Java popularized the concept of strings as immutable objects with built-in methods for searching, slicing, and concatenation—a paradigm adopted by Python, JavaScript, and many other modern languages.

2016 • AP CSP Exam Launched

The College Board introduced the AP Computer Science Principles exam, including string operations within its pseudocode reference sheet, ensuring all students encounter text processing as a core computational concept.

The central question strings address is deceptively simple: how can a computer, which fundamentally operates on numbers, faithfully represent, search within, and transform human-readable text? As you will see, the answer involves encoding schemes, indexed sequences, and a rich library of operations that the AP CSP exam expects you to understand at both a conceptual and procedural level.

SECTION 2

Core Principles & Definitions

A string is an ordered, immutable sequence of characters. Each character occupies a specific position identified by an index, and most programming languages (as well as the AP CSP pseudocode) use 1-based indexing, meaning the first character sits at index 1. Strings can contain letters, digits, spaces, punctuation, and any other characters your encoding supports. Understanding the foundational principles below will equip you to reason about virtually any string operation you encounter on the AP exam.

Ordered Sequence

Characters in a string have a defined order. The string "CAT" is different from "TAC" even though both contain the same characters. Position matters.

Indexing

Each character can be accessed by its position number. In AP CSP pseudocode, indexing starts at 1. In Python and JavaScript, indexing starts at 0. Know which convention applies.

Length

The length of a string is the total number of characters it contains, including spaces and punctuation. An empty string "" has length 0.

Concatenation

Joining two or more strings end-to-end creates a new string. CONCAT("AP", "CSP") yields "APCSP". The original strings remain unchanged.

Substring Extraction

A substring is a contiguous portion of a string. SUBSTRING(str, start, length) returns 'length' characters beginning at position 'start'.

✦

KEY TAKEAWAY

Think of a string like a row of mailboxes along a street. Each mailbox (character) has a unique house number (index), and you can always find a specific mailbox by its number, count the total mailboxes on the block (length), or describe a stretch of consecutive mailboxes (substring). You cannot rearrange the mailboxes in place—instead, you build a new street with the arrangement you want (concatenation or substring extraction).

SECTION 3

Visual Explanation — String Anatomy

The diagram above shows the string "COMPUTER" with each character in its own cell, labeled with 1-based indices. Below the character array, the three core AP CSP string operations—LENGTH, CONCAT, and SUBSTRING—are demonstrated. The dashed pink rectangle highlights the portion extracted by SUBSTRING("COMPUTER", 4, 3).

As the diagram illustrates, each character in a string is addressable by its index, making it possible to extract any contiguous subsequence. The SUBSTRING operation takes two parameters beyond the string itself: the starting index and the number of characters to extract. Meanwhile, LENGTH simply returns the total count of characters, and CONCAT joins two strings into a single new string without modifying the originals. These three operations, together with iteration, form the backbone of all string processing in the AP CSP exam.

SECTION 4

How String Operations Work

The AP CSP reference sheet defines three built-in string procedures. Understanding their precise semantics—what inputs they accept and what outputs they produce—is essential for both the multiple-choice section and the Create Performance Task. Let us formalize each operation and then explore how they compose together to solve more complex problems.

LENGTH

len ← LENGTH(str)

Returns the number of characters in str. For "HELLO", LENGTH returns 5. For an empty string "", LENGTH returns 0. Spaces count as characters.

CONCAT

result ← CONCAT(str1, str2)

Produces a new string composed of all characters of str1 followed by all characters of str2. LENGTH(result) = LENGTH(str1) + LENGTH(str2). Neither original string is modified.

SUBSTRING

sub ← SUBSTRING(str, start, length)

Returns length characters from str beginning at index start (1-based). SUBSTRING("HELLO", 2, 3) → "ELL". The start index must satisfy 1 ≤ start ≤ LENGTH(str), and start + length − 1 ≤ LENGTH(str).

Composing Operations

The true power of string operations emerges when you combine them. For instance, to extract the last character of a string s, you can write SUBSTRING(s, LENGTH(s), 1). To build a new string that prepends "Dr. " to a name, you use CONCAT("Dr. ", name). Combined with loops and conditionals, these three operations allow you to reverse strings, search for patterns, count specific characters, and perform many other text-processing tasks that appear regularly on the exam.

⚠

AP EXAM TIP

On the AP CSP exam, string indexing always starts at 1, not 0. If you are accustomed to Python or JavaScript (which use 0-based indexing), be careful to adjust when reading pseudocode. SUBSTRING("ABCDE", 1, 1) returns "A", not "B".

SECTION 5

String Traversals & Common Patterns

A string traversal is the process of visiting each character in a string one at a time, typically using a loop. Traversals are the fundamental mechanism through which algorithms search, count, filter, and transform string data. On the AP CSP exam, traversal problems require you to trace through pseudocode that iterates over a string's indices, applying operations like comparison, concatenation, or conditional logic at each step.

This diagram traces a vowel-counting traversal of the string "PROGRAM". Green-bordered cells indicate vowels (O at index 3 and A at index 6). The pseudocode on the left shows the loop structure, while the trace table on the right summarizes the two iterations where the count increments.

Common Traversal Patterns

Pattern	Description	Key Idea
Count	Count characters matching a criterion (e.g., vowels, digits, spaces)	Initialize counter to 0; increment inside conditional
Search	Find the first index of a target character or substring	Use a flag or return index when match found
Build / Transform	Construct a new string by selectively concatenating characters	Start with empty string; CONCAT matching chars each iteration
Reverse	Create a new string with characters in reverse order	Traverse from end to start, or prepend each character to accumulator

Four common string traversal patterns tested on the AP CSP exam

SECTION 6

Worked Example — Reversing a String

Let us work through a complete example of reversing the string "CODE" using only the three AP CSP string operations and a loop. This problem integrates LENGTH, SUBSTRING, and CONCAT in a single algorithm and requires careful index tracking—exactly the kind of procedural reasoning the exam tests.

Reverse the String "CODE"

1
Step 1 — Initialize Variables

Set original ← "CODE" and reversed ← "" (an empty string that will accumulate the result). Compute n ← LENGTH(original), which evaluates to 4.

n = 4, reversed = ""
2
Step 2 — Loop from Last to First Index

We iterate i from n down to 1. On each iteration, we extract the character at position i and append it to reversed. The core operation is: reversed ← CONCAT(reversed, SUBSTRING(original, i, 1))
3
Step 3 — Trace Iteration i = 4

SUBSTRING("CODE", 4, 1) returns "E". Then CONCAT("", "E") yields "E".

reversed = "E"
4
Step 4 — Trace Iteration i = 3

SUBSTRING("CODE", 3, 1) returns "D". Then CONCAT("E", "D") yields "ED".

reversed = "ED"
5
Step 5 — Trace Iterations i = 2 and i = 1

When i = 2: SUBSTRING returns "O", CONCAT("ED", "O") → "EDO". When i = 1: SUBSTRING returns "C", CONCAT("EDO", "C") → "EDOC". The loop terminates.

reversed = "EDOC"

✦

KEY TAKEAWAY

When tracing string algorithms on the exam, write out the value of every variable after each iteration—especially the accumulator string and the loop counter. Off-by-one errors are the most common mistake, and a careful trace table is your best defense. The reversal pattern (iterating backward and concatenating) is a classic template that you can adapt for many problems.

SECTION 7

Strengths, Limitations & Language Comparisons

The AP CSP pseudocode provides a deliberately simplified string interface—just three operations plus standard control structures. Real programming languages offer far richer string libraries. Understanding both the power and the constraints of the pseudocode model will help you on the exam and prepare you for actual software development.

Feature	AP CSP Pseudocode	Python	JavaScript
Index start	1 (1-based)	0 (0-based)	0 (0-based)
Length	`LENGTH(str)`	`len(str)`	`str.length`
Concatenation	`CONCAT(a, b)`	`a + b`	`a + b`
Substring	`SUBSTRING(s, i, n)`	`s[i:i+n]`	`s.substring(i, i+n)`
Search	Manual traversal required	`s.find(target)`	`s.indexOf(target)`
Case conversion	Not built in	`s.upper() / s.lower()`	`s.toUpperCase()`
Immutability	Yes (new strings created)	Yes	Yes

Comparison of string operations across AP CSP pseudocode, Python, and JavaScript

✦

KEY TAKEAWAY

The AP CSP pseudocode intentionally limits you to three string operations so that you must build more complex functionality (searching, replacing, case conversion) from scratch using loops and conditionals. This is analogous to how an engineer learns to design circuits from basic transistors before using integrated chips—the constraint forces deeper understanding of the underlying logic.

SECTION 8

Connections to Advanced Topics

String processing in AP CSP is a gateway to numerous advanced computing topics. The concepts you learn here—sequential access, pattern matching, and building new data from traversals—reappear throughout computer science in increasingly sophisticated forms. Understanding these connections will help you see why string operations are tested so thoroughly on the exam and will prepare you for future coursework.

AP CSP Concept	Advanced Extension	Real-World Application
String traversal	Iterator pattern, streaming data processing	Processing large log files line by line
Character matching in loops	Regular expressions (regex), finite automata	Email validation, search engines, spam filters
CONCAT for building strings	String builders, buffer management, O(n) vs O(n²) complexity	Web page rendering, template engines
SUBSTRING extraction	Parsing, tokenization, lexical analysis	Compilers, JSON/XML parsers, DNA sequencing
Character encoding (ASCII, Unicode)	UTF-8, UTF-16, internationalization (i18n)	Multilingual websites, emoji support

How AP CSP string concepts connect to advanced computer science topics

If you continue into AP Computer Science A or a university-level data structures course, you will encounter the StringBuilder pattern (which addresses the performance cost of repeated concatenation), regular expressions (a compact notation for describing complex string patterns), and algorithms like Knuth-Morris-Pratt for efficient substring searching. Each of these builds directly on the indexing, traversal, and extraction logic you are mastering now.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Consider the AP CSP pseudocode expression: SUBSTRING("ALGORITHM", 4, 5) What value does this expression evaluate to?

A. "ORITH"
B. "GORIT"
C. "ORITHM"
D. "LGOR"

Show answer (A)

The string "ALGORITHM" has characters at 1-based indices: A(1), L(2), G(3), O(4), R(5), I(6), T(7), H(8), M(9). SUBSTRING("ALGORITHM", 4, 5) starts at index 4 ("O") and takes 5 characters: O, R, I, T, H → "ORITH". A is correct. B ("GORIT") incorrectly starts at index 3 instead of 4. C ("ORITHM") starts correctly but takes 6 characters instead of 5. D ("LGOR") uses 0-based indexing incorrectly, starting at index 4 counting from 0.

Question 2: BASIC CALCULATION

What is the value of result after the following pseudocode executes? a ← "FIRE" b ← "WORK" result ← CONCAT(SUBSTRING(a, 1, 2), SUBSTRING(b, 2, 3))

A. "FIORK"
B. "FIRWOR"
C. "FIWOR"
D. "EWORK"

Show answer (A)

First, evaluate the inner expressions. SUBSTRING("FIRE", 1, 2) starts at index 1 and takes 2 characters → "FI". SUBSTRING("WORK", 2, 3) starts at index 2 and takes 3 characters → "ORK". Then CONCAT("FI", "ORK") → "FIORK". A is correct. B ("FIRWOR") incorrectly takes 3 characters from "FIRE" and 3 from "WORK" starting at index 1. C ("FIWOR") correctly gets "FI" but mistakenly starts the second substring at index 1. D ("EWORK") uses 0-based indexing for the first substring, taking characters at positions 1-2 in a 0-based scheme.

Question 3: INTERMEDIATE

Consider the following pseudocode: word ← "BANANA" newStr ← "" i ← 1 REPEAT LENGTH(word) TIMES { IF (SUBSTRING(word, i, 1) ≠ "A") { newStr ← CONCAT(newStr, SUBSTRING(word, i, 1)) } i ← i + 1 } Which TWO of the following statements are true about this code? (Select two.)

A. The final value of newStr is "BNN"
B. The loop iterates exactly 6 times
C. The final value of newStr is "BNNA"
D. The code modifies the original string word

Show answer (A,B)

"BANANA" has length 6, so the loop runs 6 times (B is true). Tracing through: B(1) ≠ "A" → concat; A(2) = "A" → skip; N(3) ≠ "A" → concat; A(4) = "A" → skip; N(5) ≠ "A" → concat; A(6) = "A" → skip. The non-A characters in order are B, N, N, so newStr = "BNN" (A is true). C is wrong because the algorithm filters out all instances of "A", and the last character "A" at index 6 is indeed skipped. D is wrong because strings are immutable in this context—the code builds a new string newStr and never reassigns word.

Question 4: APPLIED

3 pts

A programmer wants to write a procedure that takes a string text and a single-character string target as parameters and returns the number of times target appears in text. Write the pseudocode for this procedure using only LENGTH, SUBSTRING, CONCAT, a loop, and standard conditionals. Then trace your procedure with text = "MISSISSIPPI" and target = "S" to show the final count.

Show answer

Point 1 (Correct procedure structure — 1 pt): The procedure must accept two parameters (text and target), initialize a counter variable to 0, and use a loop that iterates LENGTH(text) times with an index variable incrementing from 1 to LENGTH(text). Point 2 (Correct comparison and counting logic — 1 pt): Inside the loop, the procedure must extract the character at the current index using SUBSTRING(text, i, 1), compare it to target using =, and increment the counter when they match. Sample pseudocode: PROCEDURE countChar(text, target) { count ← 0 i ← 1 REPEAT LENGTH(text) TIMES { IF (SUBSTRING(text, i, 1) = target) { count ← count + 1 } i ← i + 1 } RETURN count } Point 3 (Correct trace with final answer — 1 pt): For "MISSISSIPPI" (length 11) with target "S": Characters are M(1) I(2) S(3) S(4) I(5) S(6) S(7) I(8) P(9) P(10) I(11). The character equals "S" at indices 3, 4, 6, and 7. The counter increments four times, so the procedure returns 4.

Question 5: CRITICAL THINKING

4 pts

A student writes the following procedure intended to determine whether a string is a palindrome (reads the same forward and backward). The procedure should return true if the input is a palindrome and false otherwise.

PROCEDURE isPalindrome(str)
{
  reversed ← ""
  i ← LENGTH(str)
  REPEAT LENGTH(str) TIMES
  {
    reversed ← CONCAT(reversed, SUBSTRING(str, i, 1))
    i ← i + 1
  }
  RETURN (str = reversed)
}

(a) Identify the logical error in this procedure. (b) Explain what the procedure actually produces when called with isPalindrome("RACECAR"). (c) Provide a corrected version of the procedure. (d) Describe an alternative approach that checks for a palindrome without building the full reversed string, and explain why it might be more efficient.

Show answer

Point 1 — Part (a): Identify the error (1 pt): The error is in the line i ← i + 1. Since i starts at LENGTH(str) and the goal is to reverse the string, i should be decremented (i ← i − 1), not incremented. With i + 1, the index exceeds the string's length after the first iteration, causing the SUBSTRING call to access invalid indices. Point 2 — Part (b): Trace the erroneous execution (1 pt): For "RACECAR" (length 7): i starts at 7, so the first iteration correctly extracts "R" (index 7). Then i becomes 8, which exceeds the string length. Subsequent SUBSTRING calls attempt to access indices 8 through 13, which are out of bounds. Depending on the runtime, this either produces an error or undefined behavior. The procedure does not correctly reverse the string—at best it only captures the last character "R" before failing. Point 3 — Part (c): Corrected procedure (1 pt):

PROCEDURE isPalindrome(str)
{
  reversed ← ""
  i ← LENGTH(str)
  REPEAT LENGTH(str) TIMES
  {
    reversed ← CONCAT(reversed, SUBSTRING(str, i, 1))
    i ← i − 1
  }
  RETURN (str = reversed)
}

The only change is replacing i ← i + 1 with i ← i − 1 so that the loop traverses from the last character to the first, building the reversed string correctly. Point 4 — Part (d): Alternative efficient approach (1 pt): Instead of building a full reversed string, compare characters from both ends moving inward. Set left ← 1 and right ← LENGTH(str). While left < right, compare SUBSTRING(str, left, 1) with SUBSTRING(str, right, 1). If any pair differs, return false immediately. If all pairs match, return true. This approach is more efficient because it can terminate early upon finding the first mismatch (best case: one comparison), whereas the full-reversal approach always processes every character before comparing. In the worst case both approaches examine all characters, but the comparison-based approach avoids the overhead of building an entirely new string in memory.

SUMMARY

Strings — Summary

Summary

A string is an ordered, immutable sequence of characters, where each character is accessible by a 1-based index in AP CSP pseudocode. The three core operations—LENGTH (returns the number of characters), CONCAT (joins two strings into a new string), and SUBSTRING (extracts a contiguous portion given a start index and length)—form the complete toolkit for string manipulation on the AP exam.

When combined with loops and conditionals, these operations enable powerful string traversals that can count characters, search for patterns, filter content, build transformed strings, and check properties like palindrome symmetry. Remember that AP CSP uses 1-based indexing (unlike Python and JavaScript which use 0-based), and that strings are immutable—operations always produce new strings rather than modifying existing ones. Mastering careful index tracking and trace tables is essential for avoiding off-by-one errors on exam questions.